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:
- Iterative
- 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++
#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
No Responses