Welcome to Subscribe On Youtube
77. Combinations
Description
Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].
You may return the answer in any order.
Example 1:
Input: n = 4, k = 2 Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] Explanation: There are 4 choose 2 = 6 total combinations. Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
Example 2:
Input: n = 1, k = 1 Output: [[1]] Explanation: There is 1 choose 1 = 1 total combination.
Constraints:
1 <= n <= 201 <= k <= n
Solutions
Solution 1: Backtracking (Two Ways)
We design a function $dfs(i)$, which represents starting the search from number $i$, with the current search path as $t$, and the answer as $ans$.
The execution logic of the function $dfs(i)$ is as follows:
- If the length of the current search path $t$ equals $k$, then add the current search path to the answer and return.
- If $i \gt n$, it means the search has ended, return.
- Otherwise, we can choose to add the number $i$ to the search path $t$, and then continue the search, i.e., execute $dfs(i + 1)$, and then remove the number $i$ from the search path $t$; or we do not add the number $i$ to the search path $t$, and directly execute $dfs(i + 1)$.
The above method is actually enumerating whether to select the current number or not, and then recursively searching the next number. We can also enumerate the next number $j$ to be selected, where $i \leq j \leq n$. If the next number to be selected is $j$, then we add the number $j$ to the search path $t$, and then continue the search, i.e., execute $dfs(j + 1)$, and then remove the number $j$ from the search path $t$.
In the main function, we start the search from number $1$, i.e., execute $dfs(1)$.
The time complexity is $(C_n^k \times k)$, and the space complexity is $O(k)$. Here, $C_n^k$ represents the combination number.
Solution 2: Iteration
Each time the rightmost number is incremented and stored in the result res. When the right number exceeds n, the left number is increased, and then the current array is assigned to the left number, and then incremented one by one until the leftmost number is also If n is exceeded, the loop is stopped.
For n=4, k=2, the order of traversal is as follows:
0 0 #initialization
1 0
1 1
1 2 #push_back
1 3 #push_back
1 4 #push_back
1 5
2 5
2 2
2 3 #push_back
2 4 #push_back
...
3 4 #push_back
3 5
4 5
4 4
4 5
5 5 #stop
-
public class Combinations { public class Solution_dfs { List<List<Integer>> result = new ArrayList<>(); List<Integer> tmp = new ArrayList<>(); public List<List<Integer>> combine(int n, int k) { if (k > n || n <= 0 || k <= 0) { return result; } dfs(n, k, 1); return result; } private void dfs(int n, int k, int start) { if (k == 0) { result.add(new ArrayList<>(tmp)); return; } for (int i = start; i <= n; i++) { tmp.add(i); dfs(n, k - 1, i + 1); tmp.remove(tmp.size() - 1); } } } public class Solution_iteration { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> res = new ArrayList<>(); int[] out = new int[k]; int i = 0; while (i >= 0) { ++out[i]; if (out[i] > n) --i; else if (i == k - 1) res.add(Arrays.stream(out).boxed().collect(Collectors.toList())); else { ++i; out[i] = out[i - 1]; } } return res; } } } ////// class Solution { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> res = new ArrayList<>(); dfs(1, n, k, new ArrayList<>(), res); return res; } private void dfs(int i, int n, int k, List<Integer> t, List<List<Integer>> res) { if (t.size() == k) { res.add(new ArrayList<>(t)); return; } for (int j = i; j <= n; ++j) { t.add(j); dfs(j + 1, n, k, t, res); t.remove(t.size() - 1); } } } -
class Solution { public: vector<vector<int>> combine(int n, int k) { vector<vector<int>> ans; vector<int> t; function<void(int)> dfs = [&](int i) { if (t.size() == k) { ans.emplace_back(t); return; } if (i > n) { return; } t.emplace_back(i); dfs(i + 1); t.pop_back(); dfs(i + 1); }; dfs(1); return ans; } }; -
class Solution: def combine(self, n: int, k: int) -> List[List[int]]: res = [] def dfs(i, t): # no need to check len(t)>k, when '==k' returned already if len(t) == k: res.append(t.copy()) return for j in range(i, n + 1): t.append(j) dfs(j + 1, t) t.pop() dfs(1, []) # 1 to n return res class Solution_iteration: def combine(self, n: int, k: int) -> List[List[int]]: res = [] out = [0] * k i = 0 while i >= 0: out[i] += 1 if out[i] > n: i -= 1 elif i == k - 1: res.append(list(out)) else: i += 1 out[i] = out[i - 1] return res ############ class Solution(object): def combine(self, n, k): if k == 1: return [[i] for i in range(1, n + 1)] elif k == n: return [[i for i in range(1, n + 1)]] else: rs = [] rs += self.combine(n - 1, k) part = self.combine(n - 1, k - 1) for ls in part: ls.append(n) rs += part return rs -
func combine(n int, k int) (ans [][]int) { t := []int{} var dfs func(int) dfs = func(i int) { if len(t) == k { ans = append(ans, slices.Clone(t)) return } if i > n { return } t = append(t, i) dfs(i + 1) t = t[:len(t)-1] dfs(i + 1) } dfs(1) return } -
function combine(n: number, k: number): number[][] { const ans: number[][] = []; const t: number[] = []; const dfs = (i: number) => { if (t.length === k) { ans.push(t.slice()); return; } if (i > n) { return; } t.push(i); dfs(i + 1); t.pop(); dfs(i + 1); }; dfs(1); return ans; } -
public class Solution { private List<IList<int>> ans = new List<IList<int>>(); private List<int> t = new List<int>(); private int n; private int k; public IList<IList<int>> Combine(int n, int k) { this.n = n; this.k = k; dfs(1); return ans; } private void dfs(int i) { if (t.Count == k) { ans.Add(new List<int>(t)); return; } if (i > n) { return; } for (int j = i; j <= n; ++j) { t.Add(j); dfs(j + 1); t.RemoveAt(t.Count - 1); } } } -
impl Solution { fn dfs(i: i32, n: i32, k: i32, t: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) { if t.len() == (k as usize) { ans.push(t.clone()); return; } if i > n { return; } t.push(i); Self::dfs(i + 1, n, k, t, ans); t.pop(); Self::dfs(i + 1, n, k, t, ans); } pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> { let mut ans = vec![]; Self::dfs(1, n, k, &mut vec![], &mut ans); ans } }