LeetCode: Subsets

Given a set of distinct integers, S, 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 S = [1,2,3], a solution is:

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

---

We can use the same idea as compute combinations, to perform a depth first search.

C++ Code:

/*
 * func: subsets_helper
 * goal: helper function for subsets
 * @param curr: current start index
 * @param S: given set
 * @param cur_set: current subset
 * @param result: final result set
 * return:
 */
void subsets_helper(int curr, vector<int> &S, vector<int> &cur_set, vector<vector<int> > &result){
    if(curr > S.size()){
        return;
    }
    result.emplace_back(cur_set);
    for(int i = curr; i < S.size(); ++i){
        cur_set.emplace_back(S[i]);
        subsets_helper(i+1, S, cur_set, result);
        cur_set.pop_back();
    }
}

/*
 * func: subsets
 * goal: get all possible subsets of the given set
 * @param S: given set
 * return: all possible subsets
 */
vector<vector<int> > subsets(vector<int> &S){
    vector<vector<int> > result;
    vector<int> cur_set;
    subsets_helper(0, S, cur_set, result);
    return result;
}

Python Code:

# func: compute subsets of the given set
# @param S:input set
# @return: all possible subsets
def subsets(S):
    S.sort()
    result = []
    subset = []

    def subsets_helper(curr):
        if curr > len(S):
            return
        result.append(subset[:])
        for i in xrange(curr, len(S)):
            subset.append(S[i])
            subsets_helper(i+1)
            subset.pop(-1)

    subsets_helper(0)
    return result