40.combination-sum-ii.cpp

/*
 * @lc app=leetcode id=40 lang=cpp
 *
 * [40] Combination Sum II
 *
 * https://leetcode.com/problems/combination-sum-ii/description/
 *
 * algorithms
 * Medium (40.12%)
 * Total Accepted:    222.9K
 * Total Submissions: 534K
 * Testcase Example:  '[10,1,2,7,6,1,5]\n8'
 *
 * Given a collection of candidate numbers (candidates) and a target number
 * (target), find all unique combinations in candidates where the candidate
 * numbers sums to target.
 * 
 * Each number in candidates may only be used once in the combination.
 * 
 * Note:
 * 
 * 
 * All numbers (including target) will be positive integers.
 * The solution set must not contain duplicate combinations.
 * 
 * 
 * Example 1:
 * 
 * 
 * Input: candidates = [10,1,2,7,6,1,5], target = 8,
 * A solution set is:
 * [
 * ⁠ [1, 7],
 * ⁠ [1, 2, 5],
 * ⁠ [2, 6],
 * ⁠ [1, 1, 6]
 * ]
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: candidates = [2,5,2,1,2], target = 5,
 * A solution set is:
 * [
 * [1,2,2],
 * [5]
 * ]
 * 
 * 
 */
#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> tmp;
    vector<vector<int>> ans;
    void callme(vector<int>& candy, int target, int i){
        if(target == 0){
            ans.push_back(tmp);
            return;
        }
        if(i == (int)candy.size() || target<0){
            return;
        }
        tmp.push_back(candy[i]);
        callme(candy, target - candy[i], i+1);
        tmp.pop_back();
        int pp = candy[i];
        while(i+1<(int)candy.size() && candy[i+1] == pp)
            i++;
        callme(candy, target, i+1);
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        ans.clear();
        tmp.clear();
        callme(candidates, target, 0);
        return ans;
    }
};