Data Structure & Algorithms
  • 🖌️Unlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  1. Problems
  2. Backtracking

Subsets

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.

Problem Statement: Imagine you have a box of unique toys. You want to see all the different ways you can pick some toys from the box. You can pick all the toys, some of the toys, or none at all. Each different selection of toys is called a subset.

For example, if your box has 3 toys labeled 1, 2, and 3, the different subsets you can make are: no toys ([]), just toy 1 ([1]), just toy 2 ([2]), just toy 3 ([3]), toys 1 and 2 ([1,2]), toys 1 and 3 ([1,3]), toys 2 and 3 ([2,3]), and all toys ([1,2,3]).

Solution Explanation: The solution uses a method called recursion, which is like a loop but can “branch out” into multiple smaller loops.

It starts with no toys ([]) as the first subset. Then, for each toy in the box, it creates new subsets by adding that toy to all existing subsets. It does this by “branching out” into two possibilities at each step: one where it adds the current toy to the subset, and one where it doesn’t. It keeps doing this until it has tried all toys in the box.

Here’s how it works step-by-step for the box of toys [1,2,3]:

  1. Start with no toys: [[]]

  2. Try adding the first toy (1):

    • Keep the original subset without toy 1: [[]]

    • Add a new subset with toy 1: [[1]]

  3. Try adding the second toy (2):

    • Keep the original subsets without toy 2: [[], [1]]

    • Add new subsets with toy 2: [[2], [1,2]]

  4. Try adding the third toy (3):

    • Keep the original subsets without toy 3: [[], [1], [2], [1,2]]

    • Add new subsets with toy 3: [[3], [1,3], [2,3], [1,2,3]]

So the final subsets are: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]].

public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        IList<IList<int>> result = new List<IList<int>>();
        GenerateSubsets(nums, 0, new List<int>(), result);
        return result;
    }

    private void GenerateSubsets(int[] nums, int index, List<int> current, IList<IList<int>> result) {
        result.Add(new List<int>(current));
        for (int i = index; i < nums.Length; i++) {
            current.Add(nums[i]);
            GenerateSubsets(nums, i + 1, current, result);
            current.RemoveAt(current.Count - 1);
        }
    }
}

The time and space complexity of the algorithm is as follows:

Time Complexity: The time complexity is O(N * 2^N), where N is the number of elements in the input array. This is because, for each element, the algorithm branches into two recursive calls (one including the element in the subset and one excluding it), leading to 2^N possible subsets. For each subset, it takes O(N) time to make a copy of it (using new List<int>(current)) and add it to the result list.

Space Complexity: The space complexity is also O(N * 2^N). This is because there are 2^N possible subsets and each subset can take up to N space. The space is used to store the subsets in the result list and the recursive call stack.

Please note that these complexities are approximate and actual performance can vary depending on the specifics of the input and the runtime environment. Also, these complexities assume that the List.Add operation is O(1), which is generally the case in most environments but could vary. If this operation is not O(1), the time and space complexity could be higher.

PreviousTowers of HanoiNextCombination Sum

Last updated 1 year ago