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

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()
        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(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

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

class Solution(object):
  def subsets(self, nums):
    """
    :type nums: List[int]
    :rtype: 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

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