Find K-Sum Subsets

Data Structures and Algorithms

Statement

Given a set of positive integers, find all possible subsets of integers which have a sum of k.

Constraints

• 1 ≤ n ≤ 10
• 1 ≤ x ≤ 100, where x is any member of the input set
• 1 ≤ k ≤ 10³

Solution

"""
production algorithm
"""


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

    def get_k_sum_subsets_helper(self, numbers, target, n, i, sum, current, result):
        """
        time complexity O(n * 2^n)
        space complexity O(n)
        """
        if target < sum:
            return

        if sum == target:
            result.append(current[::])
            return

        for j in range(i, n):
            current.append(numbers[j])
            self.get_k_sum_subsets_helper(
                numbers, target, n, j + 1, sum + numbers[j], current, result)
            current.pop()

"""
unit tests
"""

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


class SolutionTestCase(TestCase):
    def test_no_k_sum_subsets(self):
        # Given
        numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        target = 55
        solution = Solution()

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

        # Then
        expected = set()
        self.assertEqual(actual, expected)

    def test_some_k_sum_subsets(self):
        # Given
        numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
        target = 10
        solution = Solution()

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

        # Then
        expected = {tuple([1, 2, 3, 4]), tuple([1, 2, 7]), tuple([1, 3, 6]), tuple([1, 4, 5]), tuple([1, 9]),
                    tuple([2, 3, 5]), tuple([2, 8]), tuple([3, 7]), tuple([4, 6])}
        self.assertEqual(actual, expected)

Strategy

Subsets.

Explanation

Backtracking is used to find all k sum subsets. The current subset and sum of the subset are passed as input to each step of recursion. If the sum is greater than the target, then return from backtracking. If the sum equals the target, then copy and record the subset to the result of subsets with sum k seen so far. Otherwise, the sum is less than the target, and so iterate adding and removing integers to the subset and the sum of the subset using backtracking. In the end, the result with contain all subsets with sum k.

Time Complexity

Given a set s with n elements, there are 2^n subsets of s. Also, when a subset with sum k is found, it’s copied to the result seen so far. Copying a subset has time complexity O(n). At worst, there are 2^n subsets with sum k that are copied. Therefore, the time complexity of the algorithm is O(n * 2^n).

Space Complexity

The auxiliary space complexity depends on the depth of recursion from backtracking. The depth of recursion can reach n, where n is the length of the input set. Therefore, the auxiliary space complexity of the algorithm is O(n).

Links

data_structures_algorithms/algorithms/subsets/find_k_sum_subsets at main ·…