# 21.05.2024 [78. Subsets]

All subsets #medium #backtrack

21.05.2024

78. Subsets medium
blog pos

t

youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/609

Problem TLDR

All subsets #medium #backtrack

Intuition

The are several ways to solve this:

1. DFS with a single choice: take or leave. Effectively this is a 2 ways exploration with depth of n and n copy operations at each end, so O(2 + n)^n) = O(n^n).

2. DFS with cycle from index so far until the end. The depth is the same n, however, it slighly more optimal, as we are skipping some go-in-depth invocations. The time complexity not changes.

3. DP: res[i] = nums[i] added to each of res[i - 1]. Time complexity is the same, as res[i] hold all the results and we are iterating over.

Approach

Can you make it shorter?

Complexity

• Time complexity:
  𝑂(𝑛𝑛)

• Space complexity:
  𝑂(𝑛𝑛)

Code

    fun subsets(nums: IntArray): List<List<Int>> = buildList {
        add(listOf())
        for (n in nums) for (i in indices) add(get(i) + n)
    }

    pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut res = vec![vec![]; 1]; 
        for n in nums { for i in 0..res.len() {
            res.push(res[i].iter().chain([&n]).cloned().collect())
        }}; res
    }