LeetCode-39.组合总和

╰+哭是因爲堅強的太久メ 2022-01-27 15:37 264阅读 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，指明现在遍历到了数组的第几个。**

## Java解题—回溯法 ##

class Solution {
        public List<List<Integer>> res = new ArrayList<>();
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            if(target==0) return res;
            List<Integer> list = new ArrayList<>();
            Arrays.sort(candidates);
            addSum(candidates, target, list, 0, 0);
            return res;
        }
        
        public void addSum(int[] candidates, int target, List<Integer> list, int sum, int index){
            if(sum>target) return;
            if(sum==target){
                res.add(list);
                return;
            }
            for(int i=index;i<candidates.length && candidates[i]<=target;i++){
                List<Integer> curlist = new ArrayList<>(list);
                curlist.add(candidates[i]);
                addSum(candidates, target, curlist, sum+candidates[i], i);
            }
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode:39. 组合总和

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

一时失言乱红尘/ 2024年04月03日 08:59/ 0 赞/ 99 阅读

相关 LeetCode-39. 组合总和

目录题目思路回溯题目来源 [39. 组合总和][39.] 题目思路搜索的过程抽象成树形结构如下： ![在这里插入图片描

￡神魔★判官ぃ/ 2024年03月26日 11:42/ 0 赞/ 81 阅读

相关 LeetCode - 39 组合总和

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

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

相关 leetcode 39. 组合总和

递归版本，耗时较大 include <iostream> include <vector> using namespace std;

爱被打了一巴掌/ 2023年08月17日 16:15/ 0 赞/ 138 阅读

相关【LeetCode 39】组合总和

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

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

相关 LeetCode 39. 组合总和

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

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

相关 leetcode 39 组合总和

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

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

相关 Leetcode 39. 组合总和

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

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

相关 leetcode:39.组合总和

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

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

相关 LeetCode-39.组合总和

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

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