利用递归和回溯解决LeetCode第77题：组合（Java实现）

题目

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

解法

递归

private List<List<Integer>> combine(int n, int k) {
    return add(1, n, k);
}

/**
 * 获得从from...to中所有可能的k个数组合
 */
private List<List<Integer>> add(int from, int to, int k) {
    int n = to - from + 1;  //from...to的数字个数
    List<List<Integer>> result = new ArrayList<>();
    if (n == k) {
        List<Integer> list = new ArrayList<>();
        for (int i = from; i <= to; i++) {
            list.add(i);
        }
        result.add(list);
        return result;
    }
    if (k == 1) {
        for (int i = from; i <= to; i++) {
            List<Integer> list = new ArrayList<>();
            list.add(i);
            result.add(list);
        }
        return result;
    }

    //当n > k时
    for (int i = 0; i <= n - k; i++) {
        //先递归求得某数前面的数中k-1个数的组合
        List<List<Integer>> other = add(from, to-i-1, k-1);
        //然后加上该数
        for (int j = 0; j < other.size(); j++) {
            List<Integer> curr = other.get(j);
            curr.add(to-i);
            result.add(curr);
        }
    }

    return result;
}

回溯

private int n;
private int k;
private List<List<Integer>> result = new ArrayList<>();

private List<List<Integer>> combine(int n, int k) {
    this.n = n;
    this.k = k;

    back(new ArrayList<>(), 1);
    return result;
}

private void back(List<Integer> curr, int first) {
    //满了k个数后，存入result，并回溯
    if (curr.size() == k) {
        result.add(curr);
        return;
    }

    for (int i = first; i <= n - (k - curr.size()) + 1; i++) {
        List<Integer> list = new ArrayList<>(curr);
        list.add(i);
        back(list, i + 1);
    }
}