ii 组合总和_40.组合总和II

迷南。 2023-01-09 01:08 159阅读 0赞

题目

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

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字(包括目标数)都是正整数。

解集不能包含重复的组合。

示例 1:

输入: candidates = \[10,1,2,7,6,1,5\], target = 8,

所求解集为:

\[

\[1, 7\],

\[1, 2, 5\],

\[2, 6\],

\[1, 1, 6\]

\]

示例 2:

输入: candidates = \[2,5,2,1,2\], target = 5,

所求解集为:

\[

\[1,2,2\],

\[5\]

\]

思路

沿用39题的代码，backTrack(candidates, i + 1, target - candidates\[i\], item, result);改为i+1，即当前数不可重复使用，利用flag = find(result.begin(), result.end(), if(flag == result.end())item);判断是否有重复项

\#include

\#include

using namespace std;

class Solution \{

public:

vector candidates = \{ 10, 1, 2, 7, 6, 1, 5 \};

int target = 8;

void backTrack(std::vector& candidates, int start, int target, vector item, vector>& result)

\{

if (target < 0)

\{

return;

\}

if (target == 0)

\{

vector>::iterator flag;

flag = find(result.begin(), result.end(), item);

if(flag == result.end())

\{

result.push\_back(item);

return;

\}

\}

for (int i = start; i < candidates.size(); i++)

\{

item.push\_back(candidates\[i\]);

backTrack(candidates, i + 1, target - candidates\[i\], item, result);

item.pop\_back();

\}

\}

vector> combinationSum2(vector& candidates, int target) \{

sort(candidates.begin(), candidates.end());

vector> result;

vector item;

int i = 0;

backTrack(candidates, 0, target, item, result);

sort(result.begin(), result.end());

return result ;

\}

\};

int main(int argc, char\* argv\[\])

\{

Solution sol;

auto test = sol.candidates;

auto tar = sol.target;

auto res = sol.combinationSum2(test, tar);

return 0;

\}

发表评论取消回复

表情：

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

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

相关阅读

相关 40. 组合总和 II

40. 组合总和 II 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组

柔情只为你懂/ 2024年03月30日 11:55/ 0 赞/ 75 阅读

相关 40.组合总和II

组合总和II 题目描述解题思路回溯三部曲 1. 递归函数参数 2. 递归终止条件 3. 单层搜索的逻辑

红太狼/ 2023年10月16日 13:37/ 0 赞/ 50 阅读

相关 ii 组合总和_40.组合总和II

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

迷南。/ 2023年01月09日 01:08/ 0 赞/ 160 阅读

相关【LeetCode 40】组合总和 II

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

刺骨的言语ヽ痛彻心扉/ 2022年12月05日 13:55/ 0 赞/ 132 阅读

相关 LeetCode 40. 组合总和 II

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

怼烎@/ 2022年11月01日 15:59/ 0 赞/ 179 阅读

相关 LeetCode40. 组合总和 II

给定一个数组 `candidates` 和一个目标数 `target` ，找出 `candidates` 中所有可以使数字和为 `target` 的组合。 `candidat

ゝ一世哀愁。/ 2022年05月14日 05:47/ 0 赞/ 161 阅读

相关 LeetCode 【40.组合总和 II】

LeetCode 【40.组合总和 II】题目描述：给定一个数组`candidates`和一个目标数`target`,找出`candidates`中所有可以使数字

冷不防/ 2022年04月13日 14:53/ 0 赞/ 204 阅读

相关 leetcode:40. 组合总和 II

题目连接: [https://leetcode-cn.com/problems/combination-sum-ii/description/][https_leetcod

客官°小女子只卖身不卖艺/ 2022年04月13日 02:23/ 0 赞/ 215 阅读

相关 leetcode:40.组合总和 II

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

迷南。/ 2022年02月16日 17:07/ 0 赞/ 239 阅读

相关 ✔[39]组合总和 & [40]组合总和 II

✔\[39\]组合总和 //给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target

刺骨的言语ヽ痛彻心扉/ 2021年06月22日 15:38/ 0 赞/ 411 阅读