Last Updated: 25 May, 2022

Combination Sum III

Moderate

Asked in company

Solve now

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]].

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.

Solve now

Approaches

01 Approach

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):

If we have reached the last element then we can not add any more elements so check.
The sum of elements in temp is equal to ‘n’ or not.
If it is then add it to the answer.
We can use every element once only so we will use the element greater than the previous elements.
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]]:

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

Solve now