in python write function to pick up set of unique given values to get given sum. For…
- User
in python write function to pick up set of unique given values to get given sum. For example i need to find values from array ofvalues (12,9,4,20,3) that can make sum 25
- Assistant
Certainly! To find a set of unique values from a given array that sum up to a specified total, you can use a recursive approach or dynamic programming. Below is a simple example using recursion and backtracking to achieve this.
def find_subset_sum(arr, target): # Helper function to perform backtracking def backtrack(start, target, path): if target == 0: result.append(path[:]) return for i in range(start, len(arr)): if arr[i] > target: # If the current number is greater than the target, skip continue # Take current number and move to the next index path.append(arr[i]) backtrack(i + 1, target - arr[i], path) path.pop() # Backtrack result = [] arr.sort() # Sort array to optimize and make it easier to handle backtrack(0, target, []) return result # Example usage values = [12, 9, 4, 20, 3] target_sum = 25 subsets = find_subset_sum(values, target_sum) print(f"Subsets of {values} that sum to {target_sum} are: {subsets}")Explanation:
-
Sorting and Preparation: The array is sorted to optimize and simplify the handling during recursion.
-
Backtracking Function: The
backtrackfunction is defined. It starts from a given indexstartand tries to reach thetargetsum.- If
targetis zero, it means the path we have taken forms the required sum and it is added toresult. - It iterates over the array from the current
startindex to avoid considering the same element multiple times for unique combinations. - If an element is greater than the
target, it is skipped as adding it would exceed the required sum. - The current element is added to the path, and the function calls itself recursively with the next index and reduced target.
- Backtracking is performed by removing the last added element to try other possibilities.
- If
-
Function Call and Output: The function
find_subset_sumis then called with the given array and target sum. The result is printed showing all unique subsets making up the target sum.
When you run the given code, it will output subsets from the sample array
(12, 9, 4, 20, 3)that add up to25, such as[12, 9, 4]. -