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?

Related problems

Restore IP Addresses

Subset II

Implementation

Link: http://lintcode.com/en/problem/subsets/

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> > ret;
        vector<int> path;
        int step = 0;
        helper(ret, path, nums, step);
        return ret;
    }

    void helper(vector<vector<int> > & ret, vector<int> & path, vector<int> & nums, int step){

        ret.push_back(path);

        if(step == nums.size()){
            return;
        }

        for(int i = step; i < nums.size(); i++){
            path.push_back(nums[i]);
            helper(ret, path, nums, i + 1);
            path.pop_back();
        }
    }
};