（LeetCode）Java 求解组合总和

阳光穿透心脏的1/2处 2022-10-25 12:58 84阅读 0赞

### 文章目录 ###

*   *  一、题目
     *  二、回溯分析
     *  三、代码
     *  四、剪枝优化
     *  五、总结

## 一、题目 ##

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

*  所有数字（包括 target）都是正整数。
 *  解集不能包含重复的组合。

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

## 二、回溯分析 ##

排列组合，首选回溯

（1）确定递归函数的参数

> 三个全局变量，一个存放总的结果，一个存放每次的结果，一个存放记录和

//记录整个集合
    List<List<Integer>> lists = new ArrayList();
    //这里采用双端队列，记录每轮的数据
    Deque<Integer> deque = new LinkedList<>();

> 递归参数：数组，目标数，数组下标：`backTracking(candidates,target,0);`

但是题目要求不能有重复的组合存在：比如 \[2,3,6,7\]，如果选了\[2,2,3\]，那么\[2,3,2\]，\[3,2,2\] 就不能选了

这个处理也就是每次只能往后选，也就是 2 的选择范围是 \[2,3,6,7\]，3 的选择范围是\[3,6,7\]，通俗点就是2选完了就不能再选了，具体的处理可以看代码

（2）确定递归终止条件

> 当记录和大于等于target时，必须要继续进行下去

//递归终止条件
            if (sum >= target) { 
                if (sum == target) { 
                    //这个队列转集合的方法要记住
                    lists.add(new ArrayList<>(deque));
                }
                return;
            }

注意这里因为牵扯到引用问题，所以必须存入的是新的 `ArrayList<>(deque);`

（3）确定遍历顺序

for (int i = index; i < candidates.length; i++) { 
                sum += candidates[i];
                deque.add(candidates[i]);
                //继续遍历 i 表示可重复选取
                backTracking(candidates, target, i);
                sum -= candidates[i];
                deque.pollLast();
            }

## 三、代码 ##

class Solution { 
        //记录整个集合
        List<List<Integer>> lists = new ArrayList();
    
        public List<List<Integer>> combinationSum(int[] candidates, int target) { 
            //递归回溯
            backTracking(candidates,target,0);
            return lists;
        }
        //这里采用双端队列，记录每轮的数据
        Deque<Integer> deque = new LinkedList<>();
        //设定全局sum表示每轮的总和
        int sum = 0;
        //这个 index 的设置就是排除重复的集合，保证每次的选取只能往后选
        public void backTracking(int[] candidates, int target, int index) { 
            //递归终止条件
            if (sum >= target) { 
                if (sum == target) { 
                    //这个队列转集合的方法要记住
                    lists.add(new ArrayList<>(deque));
                }
                return;
            }
            for (int i = index; i < candidates.length; i++) { 
                sum += candidates[i];
                deque.add(candidates[i]);
                backTracking(candidates, target, i);
                sum -= candidates[i];
                deque.pollLast();
            }
        }
    }

## 四、剪枝优化 ##

代码虽然判断了 sum 大于 target 时，直接return，但是for循环还在走，当sum 大于 target 时，就没必要继续进行了

但是这需要首先对 candidates 排序，这样才能保证如果 sum+arr\[i\] 大于 sum了，那么后面的i都会大于 sum 就没必要继续了

class Solution { 
        List<List<Integer>> lists = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        int sum = 0;
    
        public List<List<Integer>> combinationSum(int[] candidates, int target) { 
            //需要对 candidates 排序
            Arrays.sort(candidates);
            backTracking(candidates, target, 0);
            return lists;
        }
    
        public void backTracking(int[] arr, int target, int index) { 
            if (sum >= target) { 
                if (sum == target) { 
                    lists.add(new ArrayList(list));
                }
                return;
            }
            //如果sum+arr[i]大于target，因为已经对 arr 排过序
            //所以i后面的arr元素与sum相加均会大于target
            for (int i = index; i < arr.length && (sum + arr[i] <= target); i++) { 
                sum += arr[i];
                list.add(arr[i]);
                backTracking(arr, target, i);
                sum -= arr[i];
                list.remove(list.size() - 1);
            }
        }
    }

## 五、总结 ##

该题和前面的 递归回溯题目很类似，不过前几次写的都是字符串的相关题目，该题用到了双端队列需要记住

//这里采用双端队列，记录每轮的数据
    Deque<Integer> deque = new LinkedList<>();
    //这个队列转集合的方法要记住
    lists.add(new ArrayList<>(deque));

刚开始我用的是 `List<Integer> list = new ArrayList(); lists.add(list)`来记录每轮的元素进出，发现不行，list 是引用，lists添加的是list的地址，所以每次的变化影响全局，也就是list 的每次进出都会影响 lists，解决办法就是做一次拷贝

lists.add(new ArrayList(list));

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]: /images/20221024/35f485916c3f4d169c8a3bd4e6cf6eb2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70 1]: /images/20221024/1904ba674fc64d54a9566d103f009b4c.png