Question

Formatted question description: https://leetcode.ca/all/78.html

78. Subsets

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

@tag-array

Algorithm

For the example [1,2,3] given in the title,

  • it is an empty set at the beginning,
  • then we have to deal with 1, add 1 to the empty set, which is [1], and now we have two selves [] And [1],
  • let’s deal with 2, we add 2 to each of the previous subsets, and we can get [2], [1, 2], then all the subsets are now [], [1], [2], [1, 2],
  • in the same way, we can get [3], [1, 3], [2, 3], [1, 2, 3], plus all of previous the subsets
[]
[1]
[2]
[1 2]
[3]
[1 3]
[2 3]
[1 2 3]

Code

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Subsets {

    public class Solution {
        public List<List<Integer>> subsets(int[] nums) {

            List<List<Integer>> list = new ArrayList<>();
            if (nums == null || nums.length == 0) {
                return list;
            }

            Arrays.sort(nums); // requirement: non-descending order

            // prepare, add empty one to start looping then.
            // @note: I forgot empty
            ArrayList<Integer> empty = new ArrayList<>();
            list.add(empty);

            for (int i = 0; i < nums.length; i++) {
                int numToAdd = nums[i];
                List<List<Integer>> newlyAddedList = new ArrayList<>(list);

                for (List<Integer> each : list) {
                    ArrayList<Integer> newOne = new ArrayList<Integer>(each); // deep copy

                    newOne.add(numToAdd);
                    newlyAddedList.add(newOne);

                }

                list = newlyAddedList;
            }

            return list;
        }
    }

    class Solution_dfs {

        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> ans = new ArrayList<>();
            getAns(nums, 0, new ArrayList<>(), ans);
            return ans;
        }

        private void getAns(int[] nums, int start, ArrayList<Integer> temp, List<List<Integer>> ans) {
            ans.add(new ArrayList<>(temp)); // @note: deep copy
            for (int i = start; i < nums.length; i++) {
                temp.add(nums[i]);
                getAns(nums, i + 1, temp, ans);
                temp.remove(temp.size() - 1);
            }
        }
    }

}

All Problems

All Solutions