Q: You have 9 poker cards, numbered 1 to 9. Given two integers SUM (for example 11) and COUNT (for example, 3), construct every combination of 3 cards, who add up to the target 11.
Within each combination, if we need to generate each permutation, it’s as simple as calling next_permutation() within an array (which is a combination).
You can only choose each card 0 or 1 time, i.e. no redraw.
I used to feel this was dynamic programming. Now I feel we have no choice but iterate over all combinations. We have an algo to generate ascending combinations. We can stored them in mini arrays, each one is ascending. We could use binary search in each mini-array.
https://github.com/tiger40490/repo1/blob/cpp1/cpp/array/sizeN-subset_TargetSum_Ashish.cpp is a very short recursive solution by my friend CSY.
//There are N distinct poker cards numbered 1 to N. Find all combinations
//of C cards such that each combo adds up to the same given Target
//
//Based on https://bintanvictor.wordpress.com/2017/11/08/generate-next_combo3-boys-out5-recursive/
//
//Note some range of the generated sequence is ascending, permitting
//binary search like lower_bound, but it's not easy to tweak the algo
//to skip ahead. There's no random access iterator here!
#include <iostream>
#include <sstream>
#include <deque>
#include <iomanip> //setw
#include <algorithm> //sort
#include <assert.h>
//#define DEBUG
using namespace std;
size_t calls=0, combos=0;
size_t const C=3; //how many in each combination
size_t const Target=12;
deque<int> pool{1,3,4,5,8};
deque<int> prefix;
template<typename T> void dumpDeque(deque<T> const & p, string const & headline){
cout<<"-- "<<headline<<" -- size = "<<p.size()<<endl;
for(int i=0; i<p.size(); ++i) cout<<setw(5)<<p[i];
cout<<endl;
}
template<typename T> int showCombo(deque<T> const * p){
++ combos;
size_t sum = 0;
stringstream ss;
for(int i=0; i<p->size(); ++i){
ss<<setw(5)<<(*p)[i];
sum+= (*p)[i];
}
static string last;
string combo=ss.str();
cout<<"combo: "<<combo;
if (sum == Target) cout<<" <- Hit!";
cout<<endl;
assert(last <= combo && "should be ascending");
last = combo;
}
template<typename T> int recurs(){
++calls;
#ifdef DEBUG
cout<<"-------------\nentering "; dumpDeque(prefix, "prefix"); dumpDeque(pool, "pool");
#endif
if (prefix.size() == C) return showCombo(&prefix); //prefix alone is the combo
if (pool.empty()) return 0;
T poolhead = pool.front(); pool.pop_front();
prefix.push_back(poolhead); //add poolhead to prefix
//this 1st recursive function call starts a rather deep call stack and prints
//all combinations that start with the given (new longer) prefix
recurs<T>();//use the longer prefix and the shorter pool
prefix.pop_back();//restore prefix
recurs<T>();
pool.push_front(poolhead); //restore pool, needed by the 2nd call in the parent stack
#ifdef DEBUG
cout<<"^^^^^^ restored before returning "; dumpDeque(prefix, "prefix"); dumpDeque(pool, "pool");
#endif
}
int main() {
assert(C <= pool.size());
sort(pool.begin(), pool.end());
recurs<int>();
cout<<calls<<" calls to the recursive function to generate "<<combos<<endl;
}
keep learning 活到老学到老 