Leetcode: Subsets (8ms) Backtracking

PROBLEM:

Given a set of distinct integers, nums, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Show Tags

Analysis:

Backtracking is one solution to find all possible subsets. Problem is how to solve it with backtracking. Before coding, we need to be very clear how to construct this problem with BT. 

A possible solution is shown in the figure below:

we can see that the subset for [1 2 3] can be built based on the subset of [1 2], and the subset of [1 2] can be built on subset of [1]. We know the subset of [1], when only one item in the set. 

Based on above logic, we can easily solve this problem with BT on above logic. The left thing is coding. 

So when we plan to use BT, we at first need to find out the 'reusing' logic or the later one is built based on the current one. 

///////////////////////////////////////////////////////////

//codes 8ms

class Solution {

public:

       void searchSubset(vector<int>&nums, int inSize, vector<vector<int>> &result, int endCondition){

              //return condition

              if (inSize == 1){

                     vector<int> tmp;

                     tmp.push_back(nums[0]);

                     result.push_back(tmp);

                     return;

              }

              else{

                     while (1){

                           //forward

                           searchSubset(nums, inSize-1, result, endCondition);

                           //backward

                           int size = result.size();

                           for (int j = 0; j<size; j++){

                                  vector<int> tmp = result[j];

                                  tmp.push_back(nums[inSize - 1]);//add the last item

                                  result.push_back(tmp);

                           }

                           vector<int> tmp = { nums[inSize - 1] };//the single item

                           result.push_back(tmp);

                           //end condition check

                           if (inSize >= endCondition){

                                  vector<int>tmp;

                                  result.push_back(tmp);

                                  return;//final return

                           }

                           return;

                     }

              }

       }

       vector<vector<int>> subsets(vector<int>& nums) {

             

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

              vector<vector<int>> result;

              //check special case

              if (nums.size() == 0)return result;

              else if (nums.size() == 1){

                     vector<int>tmp;

                     result.push_back(tmp);

                     tmp.push_back(nums[0]);

                     result.push_back(tmp);

                     return result;

              }

              else { searchSubset(nums, nums.size(), result, nums.size()); }

              return result;

       }

};