Question

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

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

1 <= nums.length <= 10
-10 <= nums[i] <= 10
All the numbers of nums are unique.

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

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

}

############

class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private int[] nums;

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

    private void dfs(int u, List<Integer> t) {
        if (u == nums.length) {
            ans.add(new ArrayList<>(t));
            return;
        }
        dfs(u + 1, t);
        t.add(nums[u]);
        dfs(u + 1, t);
        t.remove(t.size() - 1);
    }
}

// OJ: https://leetcode.com/problems/subsets/
// Time: O(N * 2^N)
// Space: O(N)
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& A) {
        vector<vector<int>> ans;
        vector<int> tmp;
        function<void(int)> dfs = [&](int i) {
            if (i == A.size()) {
                ans.push_back(tmp);
                return;
            }
            tmp.push_back(A[i]);
            dfs(i + 1); // Pick A[i]
            tmp.pop_back();
            dfs(i + 1); // Skip A[i]
        };
        dfs(0);
        return ans;
    }
};

from typing import List

class Solution: # bfs
    def subsets(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return [[]]

        nums.sort() # sort() not necessary if no duplicates
        result = [[]]

        for num in nums:
            result += [subset + [num] for subset in result]

        return result


class Solution: # dfs
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def dfs(u, t):
            ans.append(t[:]) # or, t.copy()
            for i in range(u, len(nums)):
                t.append(nums[i])
                dfs(i + 1, t)
                t.pop()

        ans = []
        nums.sort() # sort() not necessary if no duplicates
        dfs(0, [])
        return ans


class Solution: # dfs, just pass down the final path
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def dfs(nums, index, path, ans):
            ans.append(path)
            [dfs(nums, i + 1, path + [nums[i]], ans) for i in range(index, len(nums))]

        ans = []
        dfs(nums, 0, [], ans)
        return ans


class Solution: # dfs, but running slower, since need to reference from parent method for 'nums' and 'ans'
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def dfs(index, path):
            ans.append(path)
            [dfs(i + 1, path + [nums[i]]) for i in range(index, len(nums))]

        ans = []
        dfs(0, [])
        return ans

func subsets(nums []int) [][]int {
	var ans [][]int
	var dfs func(u int, t []int)
	dfs = func(u int, t []int) {
		if u == len(nums) {
			ans = append(ans, append([]int(nil), t...))
			return
		}
		dfs(u+1, t)
		t = append(t, nums[u])
		dfs(u+1, t)
		t = t[:len(t)-1]
	}
	var t []int
	dfs(0, t)
	return ans
}

function subsets(nums: number[]): number[][] {
    const n = nums.length;
    const t: number[] = [];
    const res: number[][] = [];
    const dfs = (i: number) => {
        if (i === n) {
            res.push([...t]);
            return;
        }
        dfs(i + 1);
        t.push(nums[i]);
        dfs(i + 1);
        t.pop();
    };
    dfs(0);
    return res;
}

impl Solution {
    fn dfs(i: usize, t: &mut Vec<i32>, res: &mut Vec<Vec<i32>>, nums: &Vec<i32>) {
        if i == nums.len() {
            res.push(t.clone());
            return;
        }
        Self::dfs(i + 1, t, res, nums);
        t.push(nums[i]);
        Self::dfs(i + 1, t, res, nums);
        t.pop();
    }

    pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut res = Vec::new();
        Self::dfs(0, &mut Vec::new(), &mut res, &nums);
        res
    }
}

78 - Subsets

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions