网站建设企业排行榜,用新华做网站名是否侵权,旅游网站国际业务怎样做,免费seo提交工具目录 【力扣】77. 组合题解回溯回溯法三步剪枝优化 【力扣】77. 组合
给定两个整数 n 和 k#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按任何顺序返回答案。
示例 1#xff1a; 输入#xff1a;n 4, k 2 输出#xff1a;
[[2,4],[3,4],[2,3],[1,2]… 目录 【力扣】77. 组合题解回溯回溯法三步剪枝优化 【力扣】77. 组合
给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按任何顺序返回答案。
示例 1 输入n 4, k 2 输出
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]示例 2 输入n 1, k 1 输出
[[1]]提示 1 n 20 1 k n
题解
暴力思考k 等于多少就是多少层循环。
//示例中k为2
int n 4;
for (int i 1; i n; i) {for (int j i 1; j n; j) { sout(i j);}
}//示例中k为3
int n 100;
for (int i 1; i n; i) {for (int j i 1; j n; j) {for (int u j 1; u n; n) {sout(i j u);}}
}回溯
回溯法解决的问题都可以抽象为树形结构N叉树。
n 相当于树的宽度k 相当于树的深度。图中每次搜索到了叶子节点就找到了一个结果。
回溯法三步 递归函数的返回值以及参数 回溯函数终止条件 单层搜索的过程
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}import java.util.*;public class Solution {ListListInteger result new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger combine(int n, int k) {backtracking(n, k, 1);return result;}public void backtracking(int n, int k, int startIndex) {// 终止条件if (path.size() k) {//存放结果result.add(new ArrayList(path));return;}//横向遍历for (int i startIndex; i n; i) {//处理节点path.add(i);//纵向搜索backtracking(n, k, i 1);//回溯撤销处理结果path.removeLast();}}
}剪枝优化 剪枝的地方就在递归中每一层的for循环所选择的起始位置。如果 for 循环选择的起始位置之后的元素个数已经不足需要的元素个数那么就没有必要搜索了。
已经选择的元素个数path.size();还需要的元素个数为: k - path.size();在集合 n 中至多要从该起始位置 : n - (k - path.size()) 1开始遍历
for (int i startIndex; i n - (k - path.size()) 1; i) // i为本次搜索的起始位置import java.util.*;public class Solution {ListListInteger result new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger combine(int n, int k) {backtracking(n, k, 1);return result;}public void backtracking(int n , int k, int startIndex) {// 终止条件if (path.size() k) {//存放结果result.add(new ArrayList(path));return;}//横向遍历for (int i startIndex; i n - (k - path.size()) 1; i) {// i为本次搜索的起始位置//处理节点path.add(i);//纵向搜索backtracking(n, k, i 1);//回溯撤销处理结果path.removeLast();}}
}
