Last Updated: 17 Dec, 2020
Combination Sum
Easy
Asked in companies
You are given an array 'ARR' of 'N' distinct positive integers. You are also given a non-negative integer 'B'.
Your task is to return all unique combinations in the array whose sum equals 'B'. A number can be chosen any number of times from the array 'ARR'.
Elements in each combination must be in non-decreasing order.
For example:
Let the array 'ARR' be [1, 2, 3] and 'B' = 5. Then all possible valid combinations are-
(1, 1, 1, 1, 1)
(1, 1, 1, 2)
(1, 1, 3)
(1, 2, 2)
(2, 3)
Input Format
Then the first line contains two space-separated integers, 'N' and 'B', denoting the number of elements in the array and the target sum, respectively.
The second line of each test case contains 'N' space-separated integers representing the elements of the array 'ARR'.
Output Format :
The only line will contain 'Yes', if the answer is correct. Else, it will contain 'No'.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Approaches
Approach:
- We can use a backtracking approach to generate all the valid combinations.
- We have two options for every index: pick or not pick the current index element.
- If we pick the element, we have to again come back at the same index as multiple occurrences of the same element are possible, so the target reduces to target – Arr[index].
- If we decide not to pick the current element, then move on to the next index, and the target value stays as it is.
Algorithm:
- We will sort the array ‘ARR’ in ascending order.
- Let the current sum of the combination we are recursing over be ‘currSum’ and the index we are on in the array ‘ARR’ be ‘currIndex’.
- In each recursive call, we will:
- While currSum <= B:
- Increase ‘currSum’ by ARR[currIndex].
- Insert ‘ARR[currIndex]’ in ‘currList’.
- Recurse over ‘currIndex’ + 1.
- We remove all ‘ARR[currIndex]’ inserted into ‘currList’ for backtracking.
- While currSum <= B:
- The state where the ‘currSum’ is equal to B will be a valid combination, and we will include it in our final answer.
Similar problems