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

1
2
3
4
5
6
7
8
9
10
Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
  • dfs中有start参数，因为combinations从n个数中选择k个，很明显并不能有重复元素
  • 其实可以记着，只有permutations没有start这个参数，combinations之类的都有；
  • i+1也是对应了没有duplicates(因为是n中选k个)
  • k-1是类似39. Combination Sum, 每次dfs元素个数都减少，直到选择完毕k个元素

所以，并不会有Combination Sum II这种可以有duplicates的情况，因为从n个元素中选k个不可能有这种

trivial: 主函数中dfs从1开始，不是从0开始。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> list = new ArrayList<>();
        dfs(list, new ArrayList<>(), 1, n, k);
        return list;
    }

    public void dfs(List<List<Integer>> list, List<Integer> arr, int start, int n, int k) {
        if (k == 0) list.add(new ArrayList<>(arr));
        for (int i = start; i <= n; ++i) {
            arr.add(i);
            dfs(list, arr, i+1, n, k-1);
            arr.remove(arr.size() - 1);
        }
    }
}