Combination Sum III

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
29 upvotes
Asked in company
Walmart

Problem statement

You are given ‘k’ and ‘n’ and you have to do the following:-


Return all possible combinations of arrays whose elements sum is equal to ‘n’, and you can use only elements in the range '1' to '9' inclusive, and you can use each element at most once, and the size of the combination should be exactly ‘k’.


If there is no combination, return an empty array.


It should be noted that the 2-D array should be returned in sorted order, meaning the lexicographically smaller array should come first.


Also, at each index of the 2-D array, the elements present in the array present at that index should be in sorted order.


Note: 
Two combinations are called different if an element is in one combination and not in another. 

Also, in the output, you will see the 2-D array returned by you.


Example: 
Input: ‘k’ = 2, ‘n’ = ‘5’

Output: [[1, 4], [2, 3]]

Sample Explanation: 1 + 4 = 5 and 2 + 3 = 5. Only these two combinations are there, which sum up to n, so the answer is [[1, 4], [2, 3]].
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the value of ‘k’.

The second line will contain the value of ‘n’.
Output format : 
Return all possible combinations. If there is no combination, return an empty 2-D array.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Sample Input 1 :
2
5
Sample Output 1 :
1 4
2 3
Explanation Of Sample Input 1 :
1 + 4 = 5 and 2 + 3 = 5. Only these two combinations are there which sum upto n so answer is [[1, 4], [2, 3]].
Sample Input 2 :
3
8
Sample Output 2 :
1 2 5
1 3 4
Explanation Of Sample Input 2 :
1 + 2 + 5 = 8 and 1 + 3 + 4 = 8. Only these two combinations are there which sum upto n so answer is [[1, 2, 5], [1, 3, 4]].
Expected Time Complexity :
The expected time complexity is O(2^k), where k is the given integer.
Expected Space Complexity :
The expected space complexity is O(k), where k is the given integer.
Constraints :
2 <= k <= 9
1 <= n <= 60

Time Limit: 1 sec
Hint

Can you think about some backtracking solution?

Approaches (1)
Backtracking

We can use the elements in the range [1, 9] and that too each element only once. So the max sum can only be 45. We can do a recursive solution where we will add an element in the combination greater than we add in the last operation in this way will not create a similar combination again also we won’t use the same element twice and in each will add an element if the total sum is <= n if the number of elements in the combination is equal to k and sum is equal to n we will add to ‘ans’ matrix. We will return this matrix after the end of the recursion.

 

The steps are as follows:-

create(self, i: int, k: int, n: int, temp: List[int], ans: List[List[int]], last: int):

  1. If we have reached the last element then we can not add any more elements so check.
  2. The sum of elements in temp is equal to ‘n’ or not.
  3. If it is then add it to the answer.
  4. We can use every element once only so we will use the element greater than the previous elements.
  5. So for 'curr' in range [last+1, 9]
    • If 'curr' is greater than ‘n’ then we can not add it to 'temp'.
    • Add the current element to 'temp' and call the create function with n-curr.
    • BackTrack.

combinationSum3(self, k: int, n: int) -> List[List[int]]:

  1. Declare a 'ans' Matrix to store answers and one temporary array 'temp'.
  2. Call the create function with initial i= 0 as there is no element in temp.
  3. 'n' is initially 'n' as there is no element in temp.
  4. 'ans' is initially empty.
  5. The last element initially we take as 0 as we can take numbers between [1, 9].
  6. And in each case, we check from 'last'+1.
  7. Return 'ans'.
Time Complexity

O( 2^9 ).

 

We have 9 elements in total and each element can either be there in the combination or not there. So we can either pick an element or not pick the element so we have 2 choices for each element and there are 9 elements.

 

Hence the time complexity is O( 2^9 ).

Space Complexity

O( K ), Where 'k' is the number of elements in each combination.

 

We will make at most k recursive calls so there will recursive stack size of ‘k’.


Hence the space complexity is O( ‘k’ ).

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