【随想录】Day24—第七章 回溯算法part01

本文主要是介绍【随想录】Day24—第七章 回溯算法part01，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

题目1: 理论基础

---

1- 思路及回溯模板

回溯法模板

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

---

题目2: 组合

• 题目链接：77. 组合

---

1- 思路

利用回溯三部曲

• 1. 回溯参数及返回值
  • n 代表长度。控制回溯中 for 循环的截止条件
  • k 代表组合数个数，控制回溯的终止条件
  • startIndex 控制回溯过程中的起始位置。 从 1-n
• 2. 回溯终止条件
  • 当 path.size() == k 时，证明需要收集结果
• 3. 单层回溯逻辑

// 单层
for(int i = startIndex;i<=n;i++){path.add(i);backTracing(n,k,i+1);path.removeLast();
}

---

2- 题解

⭐组合 ——题解思路

class Solution {public List<List<Integer>> combine(int n, int k) {backTracing(n,k,1);return res;}List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public void backTracing(int n ,int k,int startIndex){if(path.size()==k){res.add(new ArrayList(path));return ;}// 单层for(int i = startIndex;i<=n;i++){path.add(i);backTracing(n,k,i+1);path.removeLast();}}   
}

---

这篇关于【随想录】Day24—第七章 回溯算法part01的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---