专栏首页Michael阿明学习之路LeetCode 40. 组合总和 II(排列组合 回溯)

LeetCode 40. 组合总和 II(排列组合 回溯)

1. 题目

给定一个数组 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]
]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/combination-sum-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

-类似题目 LeetCode 216. 组合总和 III(排列组合 回溯) LeetCode 39. 组合总和(排列组合 回溯)

2. 回溯求解

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> ans;
        vector<int> subset;
        bt(0,0,target,subset,ans,candidates);
        return ans;
    }
    void bt(int i, int sum, int &target, vector<int> subset, vector<vector<int>> &ans, vector<int> &candidates) 
    {
    	if(i > candidates.size() || sum > target)
    		return;
    	if(i <= candidates.size() && sum == target)
    	{
    		ans.push_back(subset);
    		return;
    	}
    	for(int j = i; j < candidates.size(); j++)
    	{
    		if(j > i && candidates[j-1] == candidates[j])//对相同的元素跳过,剪枝
    			continue;
    		subset.push_back(candidates[j]);
    		bt(j+1, sum+candidates[j], target, subset, ans, candidates);
    		subset.pop_back();
    	}
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指Offer - 面试题13. 机器人的运动范围(BFS/DFS)

    地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(...

    Michael阿明
  • LeetCode 945. 使数组唯一的最小增量(贪心)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/minimum-increment-to-make-a...

    Michael阿明
  • LeetCode 760. 找出变位映射(哈希)

    给定两个列表 A and B,并且 B 是 A 的变位(即 B 是由 A 中的元素随机排列后组成的新列表)。

    Michael阿明
  • 【每日一题】40. Combination Sum II

    Given a collection of candidate numbers (candidates) and a target number (target...

    公众号-不为谁写的歌
  • 56. 合并区间(思维)

    题目链接:https://leetcode-cn.com/problems/merge-intervals/

    Ch_Zaqdt
  • 347. 前 K 个高频元素(STL)

           虽然tag是中等难度,感觉还是比较简单的,不难想到对每一个数记录它的出现次数,然后按照出现次数从大到小排序输出就好了,主要是实现方法,这里我用了的...

    Ch_Zaqdt
  • 剑指Offer - 面试题13. 机器人的运动范围(BFS/DFS)

    地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(...

    Michael阿明
  • LeetCode 994. 腐烂的橘子(多源bfs)

           这道题刚开始看错题了,看到了图片就以为是就是从(0, 0)那个点开始,而且只有一个,然后敲完交了就wa了,然后才发现可能刚开始坏橘子有多个,而且还...

    Ch_Zaqdt
  • LeetCode - 增减字符串匹配

    原题地址:https://leetcode-cn.com/problems/di-string-match/

    晓痴
  • Sum of Two Integers

    Tyan

扫码关注云+社区

领取腾讯云代金券