Python Program
def find_subsets_with_sum(nums, target_sum):
"""
Generate all subsets of 'nums' that sum to 'target_sum'.
Parameters:
nums (list): List of integers to form subsets from.
target_sum (int): The target sum for the subsets.
Returns:
list: A list of lists, where each list is a subset summing to 'target_sum'.
"""
result = []
def backtrack(start, current_subset, current_sum):
# If the current sum is equal to the target sum, we found a valid subset
if current_sum == target_sum:
result.append(current_subset.copy())
return
# If the current sum exceeds the target, no need to continue
if current_sum > target_sum:
return
# Iterate through the numbers, starting from 'start' index
for i in range(start, len(nums)):
current_subset.append(nums[i]) # Include nums[i] in the subset
backtrack(i + 1, current_subset, current_sum + nums[i]) # Recur with updated values
current_subset.pop() # Backtrack and remove the last element added
backtrack(0, [], 0)
return result
# Example usage
if __name__ == "__main__":
numbers = [2, 4, 6, 3]
target = 6
subsets = find_subsets_with_sum(numbers, target)
print("Subsets that sum to", target, ":", subsets)
Program Explanation
Function: find_subsets_with_sum
This function takes a list of integers and a target sum, and it returns all subsets of the integers that add up to the target sum.
Parameters:
- nums (list): A list of integers from which to form subsets.
- target_sum (int): The desired sum for the subsets.
Returns:
Returns a list of lists, where each inner list is a subset that sums to target_sum.
Backtracking Function: backtrack
The backtrack function is a recursive helper function that builds subsets:
- start: The index to start from in the original list.
- current_subset: The current subset being constructed.
- current_sum: The sum of the current subset.
It works by exploring all possible combinations of the numbers. If the current_sum equals the target_sum, it adds the current_subset to the result list. If the current_sum exceeds the target_sum, it stops exploring further down that path.
Example Usage
The program includes an example usage where the list [2, 4, 6, 3] is passed along with a target sum of 6. The output will be all subsets of the list that sum to 6.
