Table of contents

• Given problem
• Using iterative version
• Using backtracking
• Wrapping up

Given problem

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

Belows are some constraints of this problem:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.
• Also, the subsets should be sorted in ascending ( lexicographic ) order.
• The list is not necessarily sorted.

For example:

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

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

Using iterative version

public static List<List<Integer>> subsetIII(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    res.add(new ArrayList<>());

    for (int value : nums) {
        List<List<Integer>> subSets = new ArrayList<>(res);

        for (List<Integer> tmp : res) {
            subSets.add(new ArrayList<>(tmp));
        }

        for (List<Integer> tmp : subSets) {
            res.add(tmp);
        }
    }

    return res;
}

The complexity of this problem:

• Time complexity: O(n * 2^n)
• Space complexity: O(n * 2^n)

Using backtracking

1. Using index is greater or equal than the array’s length to terminate backtracking

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> res = subset(nums);
        res.stream().forEach(values -> {
            System.out.print("[");
            values.stream().forEach(value -> System.out.print(value + ", "));
            System.out.print("]");
            System.out.println();
        });
    }
   
    public static List<List<Integer>> subset(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        subset(nums, res, new ArrayList<>(), 0);
        return res;
    }
   
    private static void subset(int[] nums, List<List<Integer>> res, List<Integer> values, int index) {
        res.add(new LinkedList<>(values));
   
        for (int i = index; i < nums.length; ++i) {
            values.add(nums[i]);
            subset(nums, res, values, i + 1);
            values.remove(values.size() - 1);
        }
    }
   

2. Using the size of subarrays to iterate all cases

    public static List<List<Integer>> subset(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        for (int sizeSub = 0; sizeSub <= nums.length; ++sizeSub) {
            subsetII(nums, res, new ArrayList<>(), 0, sizeSub);
        }
   
        return res;
    }
   
    public static void subset(int[] nums, List<List<Integer>> res, List<Integer> values, int index, int k) {
        if (values.size() == k) {
            res.add(new ArrayList<>(values));
            return;
        }
   
        for (int i = index; i < nums.length; ++i) {
            values.add(nums[i]);
            subsetII(nums, res, values, i + 1, k);
            values.remove(values.size() - 1);
        }
    }
   

The complexity of this problem:

• Time complexity: O(n * 2^n)
• Space complexity: O(n * 2^n)

Wrapping up

• The background of backtracking algorithm about listing all cases of a problem.
  • There are an array - currentArr to contain the result of the current operations, and an array - finalArr to contain all final results.
  • The specific condition to put currentArr to finalArr.
  • If the current operation finished, the currentArr will get out of the current result to come back the previous results. Then, continue with the next operations.

Refer:

https://www.interviewbit.com/problems/subset/