[Leetcode][第216题][JAVA][数组之和3][回溯]

ゞ浴缸里的玫瑰 2022-12-05 15:26 113阅读 0赞

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

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

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

回溯 剪树枝 当和超过n 或 个数超过k

###### 1. 正向求和 优化前 ######

class Solution { 
        public List<List<Integer>>  ans = new LinkedList();
        public List<List<Integer>> combinationSum3(int k, int n) { 
            dfs(0,k,0,n,1,new LinkedList<Integer>());
    
            return ans;
        }
    
        private  void dfs(int depth,int k,int sum,int n,int num,List<Integer> list){ 
    
            if(depth>k){ 
                return;
            }
            if(sum>n){ 
                return;
            }
    
            if(depth ==k && sum==n){ 
                ans.add(new LinkedList<Integer>(list));
                return;
            }
           
    
    
            for(int i = num;i<=9;i++){ 
                sum+=i;
                list.add(i);
                dfs(depth+1,k,sum,n,i+1,list);
                list.remove(list.size()-1);
                sum-=i;
    
            }
        }
    }

###### 2. 逆向减等0 优化后 ######

public List<List<Integer>> combinationSum3(int k, int n) { 
            List<List<Integer>> res = new ArrayList<>();
            dfs(res, new ArrayList<>(), k, 1, n);
            return res;
        }
    
        private void dfs(List<List<Integer>> res, List<Integer> list, int k, int start, int n) { 
            //终止条件，如果满足这个条件，再往下找也没什么意义了
            if (list.size() == k || n <= 0) { 
                //如果找到一组合适的就把他加入到集合list中
                if (list.size() == k && n == 0)
                    res.add(new ArrayList<>(list));
                return;
            }
            for (int i = start; i <= 9; i++) { 
                //选择当前值
                list.add(i);
                //递归
                dfs(res, list, k, i + 1, n - i);
                //撤销选择
                list.remove(list.size() - 1);
            }
        }

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

###### 1. 逆向可以减少 传参数量 ######

###### 2.在函数中调用dfs时，直接初始化变量，不用另外创建新的变量 ######

![在这里插入图片描述][2020090911180096.png_pic_center]

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

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

转载

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/f5f6ae8c97a64184846a7f0d954f00c3.png
[2020090911180096.png_pic_center]: /images/20221123/0689c648cf0845989d698c99d149adbf.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