LeetCode_79_Combinations

LeetCode

发布日期: 2022-06-06

更新日期: 2022-08-10

文章字数: 864

阅读时长: 3 分

阅读次数:

1. question: 组合（中等）

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按任何顺序返回答案。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/combinations

示例 1：

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

示例 2：

1 2	输入：n = 1, k = 1 输出：[[1]]

提示：

1 2	1 <= n <= 20 1 <= k <= n

2. answers

这道题，第一次做回溯算法，参考的题解。回溯算法的要点有两个：1. 将问题抽象成树形结构；2. 回溯销毁上一次的结果。

这道题是组合问题，回想高中的知识点：从n个数中选取k个数，第一个数有 n- k + 1个选择（因为要保证后续至少有n-1个数可选择），第二个数肯定不能包含第一个数，一定是要在第一个数的后一个数开始选择，所以它有(n-1) - (k-1) + 1个选择，第三个数则有(n-2) - (k-2) + 1个选择，以此类推。

因此，其实上面的步骤就已经将所有的选择筛选出来了，但是如何遍历呢？每个数有多个选择，那么就循环每一个选择，之后，以递归的形式进行进行下个数的选择。那么什么时候递归结束呢？构造出k个数即可。

递归构造出k个数之后，将其添加到结果中，之后，删除k个数的最后一个数，递归返回到上一步，继续遍历，这就是回溯。

public class Solution_0078_02 {

    public LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {

        recur(n, k, 1);
        return res;
    }

    public void recur(int n, int k, int startIndex) {

        if(path.size() == k) {

            // 注意，因为是引用数据类型，所以单纯地将path加入到res中后，后续修改会覆盖掉原来的结果，因此这里需要重新生成一个结果
            // 将其添加到结果中。
            res.add(new ArrayList<>(path));
            return;
        }

        // 针对k中的某个数，循环其所有可能的选择，并对后面的数递归。
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {

            // 执行操作，
            path.add(i);

            // 递归，因为递归，此语句执行结束之后，一定能找到结果
            // 注意，下个数从当前数的下一位数开始选择
            recur(n, k, i + 1);

            // 撤销上次递归找到的结果，进行下次循环递归
            path.removeLast();
        }

    }

    public static void main(String[] args) {
        System.out.println();

        Solution_0078_02 s = new Solution_0078_02();

        List<List<Integer>> result = s.combine(4, 2);

        for(List<Integer> list: result) {

            for(Integer i: list)
                System.out.print(i + "\t");

            System.out.println();
        }

    }
}