Subsets

Description

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

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

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

Challenge:
Can you do it in both recursively and iteratively?

Link

Lintcode_ladder

Method

1. dfs, recursion, finding all combination
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int> > subsets(vector<int>& nums) {
        // write your code here
      vector<vector<int>> result;
      if (nums.empty()) {
        return result;
      }
      int n = nums.size();
      vector<int> row;
      helper(result, row, nums, 0);
      return result;
    }
private:
    void helper(vector<vector<int>>& result, vector<int>& row, 
                vector<int>& nums, int start) {
        int n = nums.size();
        result.push_back(row);
        for (int i = start; i < n; ++i) {
            row.push_back(nums[i]);
            helper(result, row, nums, i+1);
            row.erase(row.begin() + row.size() -1);
        }
        return;
    }
};

Similar problems

x

Tags

x