Subsets

Problem

Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]

Output:

[

  [3],

  [1],

  [2],

  [1,2,3],

  [1,3],

  [2,3],

  [1,2],

  []

]

Solution

At each position, we can decide to include the element or not, so each position has 2 choices, the total combinations are 2^N. These 2^N choices can be represented by a binary mask. We increase i from 0 to 2^N, for each i, we call Integer.toBinaryString(i) in order to convert it to binary form. Then the binary 1 positions should be included, the binary 0 positions should not be included.

public class SubSets {
  public static void subSets(int[] a) {
    int N = a.length;
    int total = (1<<N);
    System.out.println("[");
    for(int i = 0; i < total; i++) {
      String mask = Integer.toBinaryString(i);
      System.out.print("  [");
      for(int j = 0; j < mask.length(); j++) {//0 01 10 11 100 101
        if(mask.charAt(mask.length() - 1 - j) == '1') {
          System.out.print(a[j]);
          if(j != mask.length()-1)
            System.out.print(",");
        }
      }
      if(i == total-1) {
        System.out.println("]");
      } else {
        System.out.println("],");
      }
   
    }
    System.out.println("]");
  }
  public static void main(String...args) {
    int[] a = {1,2,3};
    subSets(a);
  }
}

The time cost is O(N*2^N), because for each binary mask, we need to go through the array to decide which elements to include, which is O(N) cost operation. We don't need extra cost except few variables, the extra space is O(1).

The same problem can also be resolved with backtracking and recursive. We use a list to store the subset, then keep adding array elements into the list. Once we collected enough elements in the list, we print it out, otherwise, we add more elements from the array into list by recursively call the same function. At the end of the recursive function, the last element added into the list is removed, so that it can traceback to earlier state after try the last element.

import java.util.*;
public class SubSets {
  public static void subSets(int sz, int start, int[] a, List<Integer> result) {
    if(result.size() == sz) {
      System.out.print("  [");
      for(int i = 0; i < sz; i++) {
        System.out.print(result.get(i));
        if(i != sz-1)
          System.out.print(",");
      }
      System.out.println("],");
    }
    for(int i = start; i < a.length; i++) {
      result.add(a[i]);
      subSets(sz, i+1, a, result);
      result.remove(result.size()-1);
    }
  }
  public static void main(String...args) {
    int[] a = {1,2,3};
    System.out.println("[");
    for(int i = 1; i <= a.length; i++) {
      subSets(i, 0, a, new ArrayList<Integer>());
    }
    System.out.println("  []");
    System.out.println("]");
  }
}

The time complexity is O(N*2^N) and the extra space used is bound by the list size, which is at most O(N).