leetcode110:combination-sum-ii
阅读原文时间:2023年07月08日阅读:3

给出一组候选数C和一个目标数T,找出候选数中起来和等于T的所有组合。

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

注意:

  • 题目中所有的数字(包括目标数T)都是正整数
  • 组合中的数字 (a 1, a 2, … , a k) 要按非递增排序 (ie, a 1 ≤ a 2 ≤ … ≤ a k).
  • 结果中不能包含重复的组合

例如:给定的候选数集是[10,1,2,7,6,1,5],目标数是8

解集是:

[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

Given a collection of candidate numbers ( C ) and a target number
( T ), find all unique combinations in Cwhere the candidate numbers sums
to T .

Each number in C may only be used once in the combination.

Note:

  • All numbers (including target) will be positive integers.
  • Elements in a combination (a 1, a 2, … , a k) must be in non-descending order. (ie, a 1 ≤ a 2 ≤ … ≤ a k).
  • The solution set must not contain duplicate combinations.

For example, given candidate set10,1,2,7,6,1,5and target8, 
A solution set is: 
[1, 7]
[1, 2, 5]
[2, 6]

class Solution {
    vector< int> d;
    vector > z;
    set> s;
    
public:
    vector > combinationSum2(vector &num, int target) {
        sort(num.begin(),num.end());
        dfs(num,0,target,0);
        set> ::iterator it;
        for (it=s.begin();it!=s.end();z.push_back(*it),it++);
        return z;
        
    }
    void dfs(vector & candidates,int x ,int t, int step){
        if (x>t || x<0 )  return ;
        if (x==t){s.insert(d);}
        else
        {
            int i;
            for (i=step;i<candidates.size();i++){
                d.push_back(candidates[i]);
                dfs(candidates,x+candidates[i],t,i+1);
                d.pop_back();
            }
        }
    }
};

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章