combination Sum3 Algorithm
The combination Sum3 Algorithm is a popular problem-solving technique used in computer programming and mathematics to find all unique combinations of elements in an array that add up to a given target sum. The problem is a variant of the subset sum problem, where instead of finding any subset of the given array, the algorithm specifically searches for a combination of three elements that sum up to the target value. This algorithm is often employed in coding interviews and competitive programming, as it tests the candidate's ability to efficiently traverse and analyze data structures.
The core idea behind the combination Sum3 Algorithm is to use a combination of sorting, iteration, and two-pointer techniques to find the required triplets. First, the input array is sorted in ascending order, which helps in handling duplicate values and allows for efficient navigation. Then, the algorithm iterates through the sorted array, fixing the first element of the potential triplet and employing a two-pointer approach to find the other two elements that sum up to the target. These pointers are initialized at the beginning and end of the remaining part of the array and are adjusted inwards until a valid combination is found or the pointers cross each other. This process is repeated for each element in the array, ensuring that all unique triplets are discovered. The combination Sum3 Algorithm typically has a time complexity of O(n^2), making it an efficient solution for moderately sized input arrays.
/**
* Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used
* and each combination should be a unique set of numbers.
*
* Ensure that numbers within the set are sorted in ascending order.
* Example:
* Example 1:
*
* Input: k = 3, n = 7
*
* Output:
* [[1,2,4]]
*
* Input: k = 3, n = 9
*
* Output:
* [[1,2,6], [1,3,5], [2,3,4]]
*/
#include <iostream>
#include <vector>
void combination( std::vector<std::vector<int>> & results, std::vector<int> & curr, int k, int n, int idx ) {
if ( k == 0 && n == 0 ) {
results.push_back(curr);
return;
}
for ( int i = idx; i <= 10 - k && i <= n; ++i ) {
curr.push_back(i);
combination(results, curr, k - 1, n - i, i + 1 );
curr.pop_back();
}
}
std::vector<std::vector<int>> combinationVec( int k, int n ) {
std::vector<std::vector<int>> results;
std::vector<int> curr;
combination(results, curr, k, n, 1);
return results;
}
void printVecVec( std::vector<std::vector<int>> & vec ) {
for ( auto v : vec ) {
std::cout << "[ ";
for ( auto e : v ) {
std::cout << e << " ";
}
std::cout << "]" << std::endl;
}
}
int main() {
std::vector<std::vector<int>> results;
std::cout << "Combinations for k = 3, n = 7\n";
results = combinationVec(3,7);
printVecVec(results);
results.clear();
std::cout << "\nCombinations for k = 3, n = 9\n";
results = combinationVec(3,9);
printVecVec(results);
return 0;
}
