Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

You are given * ‘k’* and

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.

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

```
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

```
2
5
```

```
1 4
2 3
```

```
1 + 4 = 5 and 2 + 3 = 5. Only these two combinations are there which sum upto n so answer is [[1, 4], [2, 3]].
```

```
3
8
```

```
1 2 5
1 3 4
```

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

```
The expected time complexity is O(2^k), where k is the given integer.
```

```
The expected space complexity is O(k), where k is the given integer.
```

```
2 <= k <= 9
1 <= n <= 60
Time Limit: 1 sec
```