Subsets

Data Structures and Algorithms

Statement

Given an array of integers numbers, find all possible subsets of numbers, including the empty set.

Constraints

• 1 ≤ numbers.length() ≤ 10
• -10 ≤ numbers[i] ≤ 10
• All integers of numbers are unique

Solution

"""
production algorithm
"""


class Solution:
    def find_subsets(self, numbers):
        """
        time complexity O(n * 2^n)
        space complexity O(n)
        """
        n, i = len(numbers), 0
        current, result = list(), list()
        self.find_subsets_helper(numbers, n, i, current, result)
        return result

    def find_subsets_helper(self, numbers, n, i, current, result):
        """
        time complexity O(n * 2^n)
        space complexity O(n)
        """
        result.append(current[::])
        for j in range(i, n):
            current.append(numbers[j])
            self.find_subsets_helper(numbers, n, j + 1, current, result)
            current.pop()

"""
unit tests
"""

from unittest import TestCase
from algorithms.subsets.subsets.solution import Solution


class SolutionTestCase(TestCase):
    def test_single_element_array(self):
        # Given
        numbers = [1]
        solution = Solution()

        # When
        subsets = solution.find_subsets(numbers)
        actual = {tuple(subset) for subset in subsets}

        # Then
        expected = {tuple([]), tuple([1])}
        self.assertEqual(actual, expected)

    def test_multi_element_array(self):
        # Given
        numbers = [1, 3, 5]
        solution = Solution()

        # When
        subsets = solution.find_subsets(numbers)
        actual = {tuple(subset) for subset in subsets}

        # Then
        expected = {tuple([]), tuple([1]), tuple([3]), tuple([5]), tuple(
            [1, 3]), tuple([1, 5]), tuple([3, 5]), tuple([1, 3, 5])}
        self.assertEqual(actual, expected)

Strategy

Subsets.

Explanation

Backtracking is used to find all subsets. For each step of recursion of backtracking, the current subset is copied and recorded. After recording, iteration of the next steps of backtracking occurs.

Time Complexity

Given a set s, there are 2^n total subsets of s. For each subset of s, the subset is copied, which has time complexity O(n), and is then recorded. Therefore, the time complexity of the algorithm is O(n * 2^n).

Space Complexity

The maximum depth of recursion in backtracking is n. In other words, the call stack takes auxiliary space proportional to n. Therefore, the auxiliary space complexity of the algorithm is O(n).

Links

data_structures_algorithms/algorithms/subsets/subsets at main ·…