day34——回溯专题

比眉伴天荒 2024-03-31 09:44 113阅读 0赞

##### 4.组合总和 #####

[力扣题目链接][Link 1]

**思路**：抽象成树结构，因为本题中的题目描述中写道，每次枚举的时候都是从自己开始，某一个数字能不能被选择关键在于**candidates\[i\]+sum<=target**，如果满足的话就可以添加进去。

![image-20221121133147656][]

**回溯三部曲**:

*  递归函数参数

public void dfs(int[] candidates,int start,int sum,int target){
        
     }

*  递归终止条件

if(sum == target){
        
                res.add(new ArrayList(path));
                return ;
      }

*  单层搜索的逻辑

for(int i = start;i<candidates.length&&candidates[i]+sum<=target;i++){
        
                path.add(candidates[i]);
                dfs(candidates,i,sum+candidates[i],target);
                path.remove(path.size()-1);
            }

**代码实现**：

class Solution {
        
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
            Arrays.sort(candidates);
            dfs(candidates,0,0,target);
            return res;
        }
        public void dfs(int[] candidates,int start,int sum,int target){
        
            if(sum == target){
        
                res.add(new ArrayList(path));
                return ;
            }
    
            for(int i = start;i<candidates.length&&candidates[i]+sum<=target;i++){
        
                path.add(candidates[i]);
                dfs(candidates,i,sum+candidates[i],target);
                path.remove(path.size()-1);
            }
        }
    }

##### 5.组合总和II #####

[力扣题目链接][Link 2]

**思路**：

*  先排序，让重复的元素都聚在一起
 *  当我们枚举组合时，每一个数只能枚举一次，遇到重复的就跳过即可。

**抽象成树结构**  
![在这里插入图片描述][930a5f68ae1441e68c0a846aa48e7cc3.png]

**回溯三部曲**：

*  **递归函数参数**

public void dfs(int[] nums, int start, int sum,int target){
        
        }

*  **递归终止条件**

if(i > start && nums[i] == nums[i - 1]){
        // 保证每一个数只能选一次
                    continue;
                }

*  **单层搜索的逻辑**

for(int i = start; i < nums.length && sum + nums[i] <= target; i ++){
        
                if(i > start && nums[i] == nums[i - 1]){
        // 保证每一个数只能选一次
                    continue;
                }
                path.add(nums[i]);
                dfs(nums, i + 1, sum + nums[i],target);// 下一次从i + 1开始
                path.remove(path.size() - 1);
            }

**代码实现**：

class Solution {
        
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        
            Arrays.sort(candidates);
            dfs(candidates, 0, 0,target);
            return res;
        }
        public void dfs(int[] nums, int start, int sum,int target){
        
            if(sum == target){
        
                res.add(new ArrayList(path));
                return ;
            }
            for(int i = start; i < nums.length && sum + nums[i] <= target; i ++){
        
                if(i > start && nums[i] == nums[i - 1]){
        // 保证每一个数只能选一次
                    continue;
                }
                path.add(nums[i]);
                dfs(nums, i + 1, sum + nums[i],target);// 下一次从i + 1开始
                path.remove(path.size() - 1);
            }
        }
    }

**补充**：

对于（2 2 3 和 3 2 2）是同一个组合，但不是同一个序列。

used\[i-1\]=0------树层去重

used\[i-1\]=1------树枝去重

![image-20221121094336616][]

##### 6.组合总和III #####

[力扣题目链接][Link 3]

**思路**：

**k控制树的深度**–递归的深度

**n控制树的宽度**–for循环的范围

**代码实现**：

class Solution {
        
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        public List<List<Integer>> combinationSum3(int k, int n) {
        
            dfs(n,k,0,1);
            return result;
        }
        public void dfs(int targetSum,int k,int sum,int startIndex){
        
            //剪枝
            if(sum>targetSum){
        
                return;
            }
            //终止条件
            if(path.size()==k){
        
                if(sum==targetSum) result.add(new ArrayList<>(path));
                return; 
            }
            //单层逻辑
            for(int i = startIndex; i <= 9 - (k - path.size()) + 1;i++){
        
                path.add(i);
                dfs(targetSum,k,sum+i,i+1);
                path.removeLast();
            }
        }
    }

#####  #####

[Link 1]: https://leetcode.cn/problems/combination-sum/
[image-20221121133147656]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/e9a77769ae2b477fa9eeb0cb19a01086.png
[Link 2]: https://leetcode.cn/problems/combination-sum-ii/
[930a5f68ae1441e68c0a846aa48e7cc3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/1a939d1eb7d3426b9ed8a29f50cd00ca.png
[image-20221121094336616]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/d816950e0aae43b78912af8d2c446929.png
[Link 3]: https://leetcode.cn/problems/combination-sum-iii/