[Leetcode][第40题][JAVA][数组总和2][回溯][剪枝]

灰太狼 2022-12-05 10:30 125阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

#### 【解答思路】 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]

###### 1. 减法 ######

import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Deque;
    import java.util.List;
    
    public class Solution { 
    
        public List<List<Integer>> combinationSum2(int[] candidates, int target) { 
            int len = candidates.length;
            List<List<Integer>> res = new ArrayList<>();
            if (len == 0) { 
                return res;
            }
    
            // 关键步骤
            Arrays.sort(candidates);
    
            Deque<Integer> path = new ArrayDeque<>(len);
            dfs(candidates, len, 0, target, path, res);
            return res;
        }
    
        /** * @param candidates 候选数组 * @param len 冗余变量 * @param begin 从候选数组的 begin 位置开始搜索 * @param target 表示剩余，这个值一开始等于 target，基于题目中说明的"所有数字（包括目标数）都是正整数"这个条件 * @param path 从根结点到叶子结点的路径 * @param res */
        private void dfs(int[] candidates, int len, int begin, int target, Deque<Integer> path, List<List<Integer>> res) { 
            if (target == 0) { 
                res.add(new ArrayList<>(path));
                return;
            }
            for (int i = begin; i < len; i++) { 
                // 大剪枝
                if (target - candidates[i] < 0) { 
                    break;
                }
    
                // 小剪枝
                if (i > begin && candidates[i] == candidates[i - 1]) { 
                    continue;
                }
    
                path.addLast(candidates[i]);
                // 因为元素不可以重复使用，这里递归传递下去的是 i + 1 而不是 i
                dfs(candidates, len, i + 1, target - candidates[i], path, res);
    
                path.removeLast();
              
            }
        }
    
        public static void main(String[] args) { 
            int[] candidates = new int[]{ 10, 1, 2, 7, 6, 1, 5};
            int target = 8;
            Solution solution = new Solution();
            List<List<Integer>> res = solution.combinationSum2(candidates, target);
            System.out.println("输出 => " + res);
        }
    }

###### 2. 加法 ######

class Solution { 
        public List<List<Integer>> res = new ArrayList<>();
        public List<List<Integer>> combinationSum2(int[] candidates, int target) { 
            int len = candidates.length;
            boolean[] used = new boolean[len];
            Arrays.sort(candidates);
            dfs(candidates,target,new ArrayDeque<Integer>(),0,0);
            return res;
        }
        public void dfs(int[] cand,int target,Deque<Integer> temp,int sum,int index){ 
            if(sum>target) return;
            if(sum==target){ 
                res.add(new ArrayList<>(temp));
                return;
            }
            for(int i=index;i<cand.length;++i){ 
                if (i > index && cand[i] == cand[i - 1]) { 
                    continue;
                }
    
    
                temp.addLast(cand[i]);
                dfs(cand,target,temp,sum+cand[i],i+1);
                temp.removeLast();
            }
        }
    }

#### 【总结】 ####

###### 1. 剪枝说明![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3] ######

###### 2.回溯算法相关题目 ######

[\[Leedcode\]\[JAVA\]\[第46题\]\[全排列\]\[回溯算法\]][Leedcode_JAVA_46]  
[\[Leetcode\]\[第81题\]\[JAVA\]\[N皇后问题\]\[回溯算法\]][Leetcode_81_JAVA_N]  
[\[Leetcode\]\[第60题\]\[JAVA\]\[第k个排列\]\[回溯\]\[DFS\]\[剪枝\]][Leetcode_60_JAVA_k_DFS]  
[\[Leetcode\]\[第39题\]\[JAVA\]\[组合总和\]\[回溯\]\[dfs\]\[剪枝\]][Leetcode_39_JAVA_dfs]

转载链接：https://leetcode-cn.com/problems/combination-sum-ii/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-3/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/d4bf62f997f84b28810b6ab1b68b4413.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/d04b4025016f424f8f1ececfdc8be3d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/9561d24eab1742d7aa0d20b66b5d8472.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/12423b0d97974e0f9d770cbc105557cf.png
[Leedcode_JAVA_46]: https://blog.csdn.net/dadongwudi/article/details/105760561
[Leetcode_81_JAVA_N]: https://blog.csdn.net/dadongwudi/article/details/108379661
[Leetcode_60_JAVA_k_DFS]: https://blog.csdn.net/dadongwudi/article/details/108419966
[Leetcode_39_JAVA_dfs]: https://blog.csdn.net/dadongwudi/article/details/108485315