Find all distinct combinations of a given length that sum to a target
Given a positive integer n and a target, find all combinations of distinct numbers in the interval [1,9] of length n that add up to the target.
For example,
Output: [1, 2, 3, 4]
Explanation: The sum of all the elements in [1, 2, 3, 4] is 10. Only one combination is possible, since numbers cannot be repeated.
Input: n = 3, target = 3
Output: []
Explanation: The 3 smallest numbers between 1 and 9 are [1, 2, 3] and their sum is 6.
Input: n = 3, target = 12
Output:
[1, 2, 9]
[1, 3, 8]
[1, 4, 7]
[1, 5, 6]
[2, 3, 7]
[2, 4, 6]
[3, 4, 5]
We can use recursion to solve this problem. The idea is to consider every number i from 1 to 9 and recur for the remaining numbers [i+1…9] with the reduced sum target-i. To avoid printing permutations, we consider numbers in increasing order. If the combination size becomes n and the target is reached, keep track of it.
Following is the C++, Java, and Python implementation based on the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include <iostream> #include <vector> #include <vector> #include <list> using namespace std; void findCombinations(int n, int target, vector<vector<int>> &result, list<int> &curr, int starting_num) { // base case: combination is not possible if (curr.size() > n || target < 0) { return; } // if the combination size becomes `n` and the target is achieved if (curr.size() == n && target == 0) { // push the current combination to the output vector<int> r(curr.begin(), curr.end()); result.push_back(r); return; } // start from the previous number in the current combination until number `9` for (int i = starting_num; i <= 9; i++) { // add current number `i` to the solution curr.push_back(i); // recur for remaining numbers with the reduced target findCombinations(n, target - i, result, curr, i + 1); // backtrack: remove the current number from the solution curr.pop_back(); } } vector<vector<int>> findCombinations(int n, int target) { // keep track of the current combination (which may or may not lead to a solution) list<int> curr; // start from the number 1 int starting_num = 1; // find all combinations and store in result vector<vector<int>> result; findCombinations(n, target, result, curr, starting_num); return result; } int main() { int n = 3, target = 12; vector<vector<int>> result = findCombinations(n, target); for (vector<int> &row: result) { for (int i: row) { cout << i << ' '; } cout << endl; } return 0; } |
Output:
1 2 9
1 3 8
1 4 7
1 5 6
2 3 7
2 4 6
3 4 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
import java.util.*; class Main { private static void findCombinations(int n, int target, List<List<Integer>> result, Deque<Integer> curr, int starting_num) { // base case: combination is not possible if (curr.size() > n || target < 0) { return; } // if the combination size becomes `n` and the target is achieved if (curr.size() == n && target == 0) { // push the current combination to the output result.add(new ArrayList<>(curr)); return; } // start from the previous number in the current combination until number `9` for (int i = starting_num; i <= 9; i++) { // add current number `i` to the solution curr.addLast(i); // recur for remaining numbers with the reduced target findCombinations(n, target - i, result, curr, i + 1); // backtrack: remove the current number from the solution curr.removeLast(); } } public static List<List<Integer>> findCombinations(int n, int target) { // start from the number 1 int starting_num = 1; // find all combinations and store in result List<List<Integer>> result = new ArrayList<>(); findCombinations(n, target, result, new ArrayDeque<>(), starting_num); return result; } public static void main(String[] args) { int n = 3, target = 12; System.out.println(findCombinations(n, target)); } } |
Output:
[[1, 2, 9], [1, 3, 8], [1, 4, 7], [1, 5, 6], [2, 3, 7], [2, 4, 6], [3, 4, 5]]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
from collections import deque def findCombinations(n, target, result, curr=deque(), start_num=1): # base case: combination is not possible if len(curr) > n or target < 0: return # if the combination size becomes `n` and the target is achieved if len(curr) == n and target == 0: # push the current combination to the output result.append(list(curr)) return # start from the previous number in the current combination until number `9` for i in range(start_num, 10): # add current number `i` to the solution curr.append(i) # recur for remaining numbers with the reduced target findCombinations(n, target - i, result, curr, i + 1) # backtrack: remove the current number from the solution curr.pop() def find_combinations(n, target): # find all combinations and store in result result = [] findCombinations(n, target, result) return result if __name__ == '__main__': n = 3 target = 12 result = find_combinations(n, target) print(result) |
Output:
[[1, 2, 9], [1, 3, 8], [1, 4, 7], [1, 5, 6], [2, 3, 7], [2, 4, 6], [3, 4, 5]]
The time complexity of the above solution is exponential and requires additional space for the recursion (call stack).
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)