Skip to content

78 Subsets ✅

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], [] ]

Thoughts

subsets = 2 ^ n

Init solution set with empty list.

Iterating over all numbers, for each number, add it to all existing subsets, but keep the existing subests.

Say for numbers [1, 2, 3],

Init solution set to be [] 1: [], [1] 2: [],[1][2],[1,2] 3: [],[1],[2],[1,2][3],[1,3],[2,3],[1,2,3]

alt

C# Solution

using System;
using System.Collections.Generic;

namespace Algorithms.Medium
{
  public class Subsets
  {
    public static List<List<int>> Get(List<int> vs)
    {

      var ans = new List<List<int>>();
      // Might need to sort if the array is not sorted
      DFS(vs, ans, new List<int>(), 0);

      return ans;
    }

    private static void DFS(List<int> vs, List<List<int>> ans, List<int> curr, int startIndex)
    {
      ans.Add(new List<int>(curr));

      for (var i = startIndex; i < vs.Count; i++)
      {
        // Record all the subsets that include vs[i]
        curr.Add(vs[i]);
        DFS(vs, ans, curr, i + 1);

        // Remove from the present subset
        curr.RemoveAt(curr.Count - 1);
      }
    }
  }
}

C# Tests

using System.Collections.Generic;
using Algorithms.Medium;
using Xunit;

namespace AlgorithmTests.Medium
{
  public class SubsetsTest
  {
    [Fact]
    public void TestName()
    {
      Assert.Equal(new List<List<int>> {
          new List<int> {},
          new List<int> {1},
          new List<int> {1, 2},
          new List<int> {1, 2, 3},
          new List<int> {1, 3},
          new List<int> {2},
          new List<int> {2, 3},
          new List<int> {3}
          }, Subsets.Get(new List<int> { 1, 2, 3 }));
    }
  }
}

Iterative:

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        if (nums == null)
            return null;
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        result.add(new ArrayList<Integer>());
        List<List<Integer>> toAddAll = new ArrayList<List<Integer>>();
        for (int i = 0; i < nums.length; i++) {
            toAddAll.clear();
            //get sets that are already in result
            for (List<Integer> a : result) {
                List<Integer> toAdd = new ArrayList<Integer>(a);
                toAdd.add(nums[i]);
                toAddAll.add(toAdd);
            }
            result.addAll(toAddAll);
        }
        //add empty set
        return result;
    }
}