组合_回溯法_java
组合
leetcode链接
问题描述
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
提示：
1 <= n <= 20
1 <= k <= n
示例
示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
示例 2：
输入：n = 1, k = 1
输出：[[1]]
解题思路
这是一道组合问题。第一眼看过去我们就能想到使用蛮力法，采用n重for循环。但细想后会发现n是一个变量我们无法真的将所有的for循环写出来。所以本题的正确解法是采用递归的回溯法。同时根据题目的约束条件进行优化剪枝操作。
代码实现
class Solution {//使用类内属性，减少递归过程中的空间消耗List<List<Integer>> result = new ArrayList();List<Integer> path = new LinkedList();public List<List<Integer>> combine(int n, int k) {tryCombine(1, n, k);return result;}//start...end为集合中可选元素，size为所需子集大小public void tryCombine(int start, int end, int size) {if (path.size() == size) {//若取到叶子结点将满足要求的子集加入结果集中result.add(new ArrayList(path));return;}//进行剪枝操作，该层循环可取的元素值不能大于end - (size - path.size()) + 1, 其中size - path.size()为还需取的元素个数。 //否则最终集合中没有足够的元素使子集达到size大小for (int i = start; i <= end - (size - path.size()) + 1; i++) {//拓展一个结点path.add(i);tryCombine(i + 1, end, size);//回溯，回到父结点从而拓展新的子结点path.removeLast();}}}