77. Combinations

求从1..n的组合，和combination sum很像，只是条件略微简单，当k（需要选的数字）减少为0时递归结束

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

public List<List<Integer>> combine(int n, int k) {
    // boundary check
    if (n <= 0 || k <= 0 || k > n) return new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    dfs(path, res, n, k, 1);
    return res;
}

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

debug代码:

public List<List<Integer>> combine(int n, int k) {
    // boundary check
    if (n <= 0 || k <= 0 || k > n) return new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    dfs(n, k, res, path, 1);
    return res;
}

private void dfs(int n, int k, List<List<Integer>> res, List<Integer> path, int index) {
    if (path.size() == k) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = index; i <= n - (k - path.size()) + 1; i++) {
        System.out.println("level " + path.size() + " add " + i + " to path " + path);
        path.add(i);
        dfs(n, k, res, path, i + 1);
        System.out.println("remove " + path.get(path.size() - 1));
        path.remove(path.size() - 1);
    }
}

level 0 add 1 to path []
level 1 add 2 to path [1]
remove 2
level 1 add 3 to path [1]
remove 3
level 1 add 4 to path [1]
remove 4
remove 1
level 0 add 2 to path []
level 1 add 3 to path [2]
remove 3
level 1 add 4 to path [2]
remove 4
remove 2
level 0 add 3 to path []
level 1 add 4 to path [3]
remove 4
remove 3
level 0 add 4 to path []
remove 4