LeetCode Entry

78. Subsets

21.05.2024 medium 2024 kotlin rust

All subsets

78. Subsets medium blog post substack youtube https://youtu.be/xRtcs1VgxXg

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: \(O(n^n)\)

• Space complexity: \(O(n^n)\)

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
    }