LeetCode3939. 组合总和

雨点打透心脏的1/2处 2022-05-14 05:09 131阅读 0赞

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

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

**说明：**

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

**示例 1:**

输入: candidates = [2,3,6,7], target = 7,
    所求解集为:
    [
      [7],
      [2,2,3]
    ]

**示例 2:**

输入: candidates = [2,3,5], target = 8,
    所求解集为:
    [
      [2,2,2,2],
      [2,3,3],
      [3,5]
    ]

--------------------

思路：回溯算法。从index=0开始遍历，直到index=candidates.length-1。

![70][]

class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> res = new LinkedList<List<Integer>>();  //保存结果集
    		List<Integer> tmp = new LinkedList<>();  //保存符合条件的数
    		Arrays.sort(candidates);  //将数组升序排序
    		
    		solve(res,0,0,tmp,candidates,target);
    		return res;
        }
        private  void solve(List<List<Integer>> res,int currentIndex,int count,List<Integer> tmp,int[] candidates,int target) {
    		 if(count>=target) {
    	            if(count==target)
    	                res.add(new LinkedList<>(tmp));
    	            return;
    	        }
    		 
    		 for(int i = currentIndex;i<candidates.length;i++){
    	            if(count+candidates[i]>target){
    	                break;
    	            }
    	            tmp.add(candidates[i]);
    	            solve(res,i,count+candidates[i],tmp,candidates,target);
    	            tmp.remove(tmp.size()-1);
    	        }
    	}
    }

[70]: /images/20220514/971a965840304171be17ad89b1c12e0b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，131人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - 39 组合总和

目录题目来源题目描述示例提示题目解析算法源码 -------------------- 题目来源 [39. 组合总和 - 力扣（LeetCod

￡神魔★判官ぃ/ 2023年09月26日 11:25/ 0 赞/ 40 阅读

相关【LeetCode 39】组合总和

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

深碍√TFBOYSˉ_/ 2022年12月05日 05:15/ 0 赞/ 144 阅读

相关 LeetCode 39. 组合总和

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

痛定思痛。/ 2022年11月01日 15:58/ 0 赞/ 172 阅读

相关 leetcode 39 组合总和

前言题目：[39. 组合总和][39.] 参考题解：[组合总和-代码随想录][-] -------------------- 提交代码画出树状图，代码思路

我会带着你远行/ 2022年09月12日 11:51/ 0 赞/ 165 阅读

相关 Leetcode 39. 组合总和

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

旧城等待，/ 2022年09月09日 04:36/ 0 赞/ 195 阅读

相关 LeetCode3939. 组合总和

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

雨点打透心脏的1/2处/ 2022年05月14日 05:09/ 0 赞/ 132 阅读

相关 LeetCode 组合总和 Ⅳ

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。示例: nums = [1, 2, 3] target = 4

ゞ浴缸里的玫瑰/ 2022年04月08日 09:47/ 0 赞/ 210 阅读

相关【leetcode】组合总和 II

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

红太狼/ 2022年03月11日 10:10/ 0 赞/ 217 阅读

相关 leetcode:39.组合总和

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

朱雀/ 2022年02月16日 04:53/ 0 赞/ 215 阅读

相关 LeetCode-39.组合总和

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

╰+哭是因爲堅強的太久メ/ 2022年01月27日 15:37/ 0 赞/ 233 阅读