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]
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;
}
}