LeetCode [77] Combinations

 77. Combinations

Medium

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

You may return the answer in any order.

 

Example 1:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Example 2:

Input: n = 1, k = 1
Output: [[1]]

 

Constraints:

• 1 <= n <= 20
• 1 <= k <= n

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

//C++ class Solution { public: vector<vector<int>> combine(int n, int k) { vector<vector<int>> res; if(!n||!k) return res; vector<int> cur; bt(n, k, res, cur, 0, 0); } void bt(int n, int k, vector<vector<int>> &res, vector<int> cur, int pos, int size){ if(size==k){ res.push_back(cur); }else if(pos<=n-k+size){ bt(n, k, res, cur, pos+1, size); cur.push_back(pos+1); bt(n, k, res, cur, pos+1, size+1); } } }; //Java class Solution { List<List<Integer>> ret = new ArrayList<>(); public List<List<Integer>> combine(int n, int k) { helper(new ArrayList<>(), n, k, 1); return ret; } void helper(List<Integer> cur, int n, int k, int i) { if(cur.size()==k){ ret.add(new ArrayList<Integer>(cur)); }else{ for(int j=i; j<=n; ++j){ if(n-j+1+cur.size()<k) break; cur.add(j); helper(cur, n, k, j+1); cur.remove(cur.size()-1); } } } }