# 77. Combinations

• Time: $O(C(n, k) \cdot k)$
• Space: $O(C(n, k))$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: vector> combine(int n, int k) { vector> ans; dfs(n, k, 1, {}, ans); return ans; } private: void dfs(int n, int k, int s, vector&& path, vector>& ans) { if (path.size() == k) { ans.push_back(path); return; } for (int i = s; i <= n; ++i) { path.push_back(i); dfs(n, k, i + 1, move(path), ans); path.pop_back(); } } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public List> combine(int n, int k) { List> ans = new ArrayList<>(); dfs(n, k, 1, new ArrayList<>(), ans); return ans; } private void dfs(int n, int k, int s, List path, List> ans) { if (path.size() == k) { ans.add(new ArrayList<>(path)); return; } for (int i = s; i <= n; ++i) { path.add(i); dfs(n, k, i + 1, path, ans); path.remove(path.size() - 1); } } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution: def combine(self, n: int, k: int) -> List[List[int]]: ans = [] def dfs(s: int, path: List[int]) -> None: if len(path) == k: ans.append(path.copy()) return for i in range(s, n + 1): path.append(i) dfs(i + 1, path) path.pop() dfs(1, []) return ans