Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]

Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

The problem can be solved in 2 ways:

1. Iterative
2. Backtracking

Solution 1: Iterative Solution.

In this solution, we take 2 loops, outer loop and inner loop. Then we start adding the elements iteratively.

Using [1, 2, 3] as an example, the iterative process is like:

Initially set: [[]]
After the first iteration, the subset will be: [[], [1]];
After the second iteration, the subset will be: [[], [1], [2], [1, 2]];
After the third iteration, the subset will be: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]].

Solution in C++

/*
* File     : get_subsets.cpp
*/
#include<iostream>
#include<vector>

using namespace std;

vector<vector<int>> get_subsets_iterative(vector<int>& input_set) 
{
  vector<vector<int>> result_set(1, vector<int>());

  for (int i = 0; i < input_set.size(); i++) 
  {
    int n = result_set.size();
    for (int j = 0; j < n; j++) 
    {
      result_set.push_back(result_set[j]); 
      result_set.back().push_back(input_set[i]);
    }
  }
  return result_set;
}


void subsets(vector<int>& nums, int start, vector<int>& temp, vector<vector<int>>& final_set) 
{
  final_set.push_back(temp);
  for (int i = start; i < nums.size(); i++) 
  {
    temp.push_back(nums[i]);
    subsets(nums, i + 1, temp, final_set);
    temp.pop_back();
  }
}


vector<vector<int>> get_subsets_backtrack(vector<int>& nums) 
{
  vector<vector<int>> final_set;
  vector<int> temp;
  subsets(nums, 0, temp, final_set);
  return final_set;
}



int main()
{
  vector<int> input_set = {1, 2, 3};

  //vector< vector<int> >result = get_subsets_iterative(input_set);
  vector< vector<int> >result = get_subsets_backtrack(input_set);



  for (int i = 0; i < result.size(); i++)
  {
    for (int j = 0; j < result[i].size(); j++)
    {
      cout<< result[i][j]<<" ";
    }
    cout<<endl;
  }
}

Output:

1
2
1 2
3
1 3
2 3
1 2 3