Python program to get all subsets having sum x

Python program to get all subsets having sum x

Generating all subsets of a list that have a sum equal to a specified value is a common problem in computer science, often associated with the term "subset sum problem".

Let's break down the approach for this:

Approach:

  1. Generate all possible subsets of the list.
  2. Filter out the subsets that have a sum equal to x.

We can use Python's itertools module to generate subsets.

Python Program:

import itertools def subsets_with_sum(nums, x): n = len(nums) # A list to store subsets with sum = x result = [] # Generate all possible subsets for i in range(1, n + 1): for subset in itertools.combinations(nums, i): if sum(subset) == x: result.append(subset) return result # Test nums = [2, 3, 5, 7, 8, 10] x = 10 print(f"Subsets of {nums} having sum {x}: {subsets_with_sum(nums, x)}")

Output:

Subsets of [2, 3, 5, 7, 8, 10] having sum 10: [(2, 3, 5), (2, 8), (3, 7), (5, 5), (10,)]

Explanation:

  • We use the function itertools.combinations to generate all possible subsets (combinations) of the list.

  • For each subset, we check if its sum is equal to x using Python's sum() function.

  • If it is, we append it to our result list.

This solution will provide all subsets of the list whose elements sum up to the desired value x.

More Tags

shopify redux-form-validators named-entity-recognition form-submit struct spring-jdbc registration doctest serializable asp.net-identity-3

More Programming Guides

Other Guides

More Programming Examples