Combinations(Medium)

LeetCode Source

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

For example, If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

解题思路：回溯+DFS

复杂度

时间复杂度最坏情况O(n!)空间栈一样O(n!)

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if (n <= 0 || k <= 0) {
        return res;
    }
    List<Integer> tem = new ArrayList<Integer>();
    helper(tem, res, 1, n, k);
    return res;
}
public void helper(List<Integer> tem, List<List<Integer>> res, int index, int n, int k) {
    if (tem.size() == k) {
        res.add(new ArrayList<Integer>(tem));
        return;
    }
    for (int i = index; i <= n; i++) {
        tem.add(i);
        helper(tem, res, i + 1, n, k);
        tem.remove(tem.size() - 1);
    }
}

References

1 Combination Sum III