LeetCode 39. 组合总和

痛定思痛。 2022-11-01 15:58 167阅读 0赞

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

//写法一：自己写的 38% 先排序，然后往后顺着往后选
    class Solution {
        
        List<List<Integer>> res;
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
            res = new ArrayList<List<Integer>>();
            Arrays.sort(candidates);
            dfs(target, candidates, 0, new ArrayList<Integer>());
            return res;
        }
        private void dfs(int target, int[] candidates, int start, List<Integer> tmp){
        
            if(target < 0)
                return;
            if(target == 0){
        
                res.add(new ArrayList<Integer>(tmp));
                return;
            }
            for(int i = start; i < candidates.length; i++){
        
                target -= candidates[i];
                tmp.add(candidates[i]);
                dfs(target, candidates, i, tmp);
                tmp.remove(tmp.size() - 1);
                target += candidates[i];
            }
        }
    }

//写法二： 77% 官方 选和不选两种情况，选的话下标不变，不选下标加1
    //链接：https://leetcode-cn.com/problems/combination-sum/solution/zu-he-zong-he-by-leetcode-solution/
    class Solution {
        
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
            List<List<Integer>> ans = new ArrayList<List<Integer>>();
            List<Integer> combine = new ArrayList<Integer>();
            dfs(candidates, target, ans, combine, 0);
            return ans;
        }
    
        public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
        
            if (idx == candidates.length) {
        
                return;
            }
            if (target == 0) {
        
                ans.add(new ArrayList<Integer>(combine));
                return;
            }
            // 直接跳过
            dfs(candidates, target, ans, combine, idx + 1);
            // 选择当前数
            if (target - candidates[idx] >= 0) {
        
                combine.add(candidates[idx]);
                dfs(candidates, target - candidates[idx], ans, combine, idx);
                combine.remove(combine.size() - 1);
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/45526a78986642afaf723b6b0f27d600.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70 1]: /images/20221024/914fe5d1f91949b4bfb3586eb022da9a.png