Subsets

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

Example

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

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

Solution

这道题是典型的隐式图题型，这种题的技巧就是可以画出DFS的便利树，与Permutations 的区别就是，它是每个节点都需要纪录进入结果数组，而后者是最后一层纪录进入。

class Solution:
    """
    @param S: The set of numbers.
    @return: A list of lists. See example.
    """
    def subsets(self, nums):
        # write your code here
        if nums == None:
            return []
        result = []
        nums.sort()
        self.dfs(nums, result, [], 0)
        return result 
    def dfs(self, nums, result, current, pos):
        result.append(list(current))
        for i in range(pos, len(nums)):
            current. append(nums[i])
            self.dfs(nums, result, current, i + 1)
            del current[-1]

public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        Array.Sort(nums);
        IList<IList<int>> result = new List<IList<int>>();
        List<int> current = new List<int>();
        DFS(nums, result, current, 0);

        return result;
    }

    public void DFS(int[] nums, IList<IList<int>> result, List<int> current, int pos){
        result.Add(new List<int>(current));
        for(int i= pos; i < nums.Length; i++){
            current.Add(nums[i]);
            DFS(nums, result, current, i + 1);
            current.RemoveAt(current.Count - 1);
        }

    }
}

public class Solution {
    public IList<IList<int>> SubsetsWithDup(int[] nums) {
        Array.Sort(nums);
        IList<IList<int>> result = new List<IList<int>>();
        List<int> current = new List<int>();
        DFS(nums, result, current, 0);
        return result;
    }

    public void DFS(int[] nums, IList<IList<int>> result, List<int> current, int pos){
        result.Add(new List<int>(current));
        for(int i= pos; i < nums.Length; i++){
            if(i > 0 && nums[i] == nums[i - 1] && i > pos){
                continue;
            }
            current.Add(nums[i]);
            DFS(nums, result, current, i + 1);
            current.RemoveAt(current.Count - 1);
        }
    }
}