Number Cmb | Backtracking | C++ Solution
Number Cmb, is a Backtracking related problem and in this post we will see how we can solve this challenge in C++
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note: All numbers (including target) will be positive integers. Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak). The combinations themselves must be sorted in ascending order. CombinationA > CombinationB iff (a1 > b1) OR (a1 = b1 AND a2 > b2) OR … (a1 = b1 AND a2 = b2 AND … ai = bi AND ai+1 > bi+1) The solution set must not contain duplicate combinations. Example, Given candidate set 2,3,6,7 and target 7, A solution set is:
[2, 2, 3]  backtracking function Corner case: when there are duplicates try the remaining numbers since the numbers are sorted ,if the sum becomes greater than k on adding the current number then it is not possible further for storing the solution
Please check the main.cpp snippet for the solution.
This solution originally posted at: Github by @susantabiswas