competetive-programming/backtracking-subset.cpp at main · kritsid/competetive-programming · 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
42
43
/*Given a set of distinct integers, S, return all possible subsets.
  Example :

If S = [1,2,3], a solution is:

[
  [],
  [1],
  [1, 2],
  [1, 2, 3],
  [1, 3],
  [2],
  [2, 3],
  [3],
]
*/

void solve(vector<bool>&visited, vector<int>arr,vector<int>&v,vector<vector<int>>&ans,int index){
    // if(v.size()==arr.size()){
        ans.push_back(v);
        // return;
    // }
    for(int i=index;i<arr.size();i++){
            v.push_back(arr[i]);
            solve(visited,arr,v,ans,i+1);
            v.pop_back();
    }
}
vector<vector<int> > Solution::subsets(vector<int> &arr) {
     vector<vector<int>>ans;
    sort(arr.begin(),arr.end());
    if(arr.size()==0){
        ans.push_back({});
        return ans;
    }

    vector<bool>visited(arr.size(),false);
    vector<int>v;

    // ans.push_back({});
    solve(visited,arr,v,ans,0);
    return ans;
}