リュックサックタイプの問題


タイトル:
2つの整数nとmを入力し、数列1,2,3から.....nの中で勝手にいくつかの数を取って、
これとmを等しくするには、その中のすべての可能な組合せを列挙することが要求される.
考え方:再帰のたびに、現在の要素を数列に追加するかどうかを考慮し、ある値に達するまで知る.
コード実装:

view plaincopy to clipboardprint?
#include<iostream>  
#include<deque>  
using namespace std;  
  
 void findNums(int n,int leftSum,deque<int>& deq)  
 {  
       if(n<0||leftSum<0)return;    //       ,    
       if(leftSum>0)  
       {  
           deq.push_front(n);              // n           
           findNums(n-1,leftSum-n,deq);  
           deq.pop_front();  
           findNums(n-1,leftSum,deq);  
       }  
       else {                      //            ,     
           deque<int>::iterator i=deq.begin();  
           for(;i!=deq.end();++i)  
           {  
               cout<<*i<<" ";  
           }  
           cout<<endl;  
       }  
 }  
  
int main()  
{  
    deque<int> myDeq;  
    findNums(10,35,myDeq);  
    return 0;  
}  

同類テーマ:
タイトル:昇順で並べ替えられた配列と数値を入力します.
配列の中で2つの数を探して、それらの和がちょうど入力された数字になるようにします.
要求時間複雑度はO(n)である.複数対の数字の和が入力に等しい数字があれば、いずれかのペアを出力すればよい.
たとえば、配列1、2、4、7、11、15、および数字15を入力します.4+11=15のため、4と11が出力される.
考え方:この問題に対して1つの配列の記録を増やせばいいです.他は同じです.
同期ブログ:http://blog.csdn.net/moxiaomomo/archive/2011/05/24/6441831.aspx