LEETCODE/combinations.cpp at master · Salah856/LEETCODE · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    void combinations(int ind,int target,vector<int> &arr,vector<vector<int>> &ans,vector<int> &ds)
    {
        if(target == 0)
        {

            ans.push_back(ds);

            return;
        }


        for(int i = ind;i < arr.size(); i++)
        {

            if(i > ind && arr[i] == arr[i-1]) continue;

            if(arr[i] > target) break;

            ds.push_back(arr[i]);

            combinations( i + 1, target-arr[i], arr, ans, ds);

            ds.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {

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

        vector<vector<int>> ans;

        vector<int> ds;

        combinations(0,target,candidates,ans,ds);

        return ans;
    }
};