Combination Sum

Easy
0/40
Average time to solve is 15m
profile
Contributed by
90 upvotes
Asked in companies
UberFacebookLinkedIn

Problem statement

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)
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
3 8
2 3 5
Sample Output 1:
Yes
Explanation Of Sample Input 1 :
All possible valid combinations are:
2 2 2 2
2 3 3
3 5
Sample Input 2 :
3 5
1 2 3
Sample Output 2:
Yes
Constraints:
1 <= 'N' <= 15
1 <= 'B' <= 20
1 <= 'ARR[i]' <= 20

Time Limit: 1sec
Hint

Try to think about a recursive solution

Approaches (1)
Recursive Approach

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.
  • The state where the ‘currSum’ is equal to B will be a valid combination, and we will include it in our final answer.
Time Complexity

O(2^N), where N denotes the number of elements of the array ‘ARR’.

 

Since we are recursing over all possible combinations of the array ‘ARR’, the time complexity will be O(2^N).

Space Complexity

O(N*2^N), where N denotes the number of elements of the array ‘ARR’.

 

The space complexity due to the recursion stack will be O(2^N). For each possible state, we store all possible elements in ‘currList’. Hence, overall space complexity will be O(N*2^N).

Code Solution
(100% EXP penalty)
Combination Sum
Full screen
Console