給定一個非遞減的序列，要求從這些序列中找出一系列的數相加等于要求的數。這題的主要任務就是怎樣去重。

　　現分析如下：

　　對于給定的兩個非遞減序列,A, B, C, D 用來映射各個數的位置，2(A) 1(B) 1(C) 1(D) 以及 2(A) 2(B) 2(C) 1(D)， 要求求出和為3的表達式。 顯然前面的序列遞歸下去會首先出現A+ B的組合，由于此時A+ B已經等于了3，所以遞歸就會回溯，此時會形成A+ C的組合，按照正常人的思維，這個解肯定是不能夠取的，但是計算機有這么聰明嗎？顯然還是要我們來設計各種復雜的判斷...... 轉回正題，我們在遞歸時有一個屬性就是遞歸的層數，而該題的求解就會與這個層數扯上關系，對于兩個相鄰且大小相等的點是要特殊考慮的，為什么呢，從上面給定的兩個序列可以看出來，（重復就是因為這些相同的數字帶來的），而且這個序列是已經相當于排好序的，這點同樣很重要。那么對于相同的數（同樣一定會是相鄰的）在深入的遞歸過程中是可以取的（可以理解為此時的和還未等于要求值，相同的數仍有利用價值）。那么對于同一層的相同數呢，呵呵，這是不能夠取的，為什么呢？首先對于該種組合的狀態是不是已經搜索過了，唯一有變化的就是所剩數字的差別了，在此而言，就是相對與上一相同的狀態少了這個數而已。這樣可能比較抽象，就拿 2 2 2 1 這個序列來說吧，2與后面的2都不能組合，因為其值超過了限定值3，最后和1組合即 A+ D= 3，對于第二個2 即B， 此時B與A是同一層的遞歸下，如果取 B 的話，那么同當時取 A 就一樣了，都是在接下來的序列中尋找和為（3- 2）的組合，然而上次的選擇范圍是（B, C, D）三個數，這次只剩下（C, D）兩個數了，所以可以得出上次搜索的解一定包括這次去搜索得到的解，因此就出現重復了。證畢。

　　代碼如下：

#include <cstdio> #include <cstring> #include <cstdlib> using namespace std;int t, n, num[105], rec[105];void DFS( int sum, int pos, int cnt, int &ans ) {if( sum== t ){ans= 1;for( int i= 1; i<= cnt; ++i ){printf( i== 1? "%d": "+%d", num[ rec[i] ] );}puts( "" );return;}for( int i= pos+ 1; i<= n; ++i ){ if( num[i]!= num[i- 1]|| i== pos+ 1 ){// 前面的就是判定同一層不能計算相鄰且大小相等的數，后面的處理不同層的相鄰的相同的數if( t>= sum+ num[i] ){rec[cnt+ 1]= i;DFS( sum+ num[i], i, cnt+ 1, ans );}}} }int main() {while( scanf( "%d %d", &t, &n ), t| n ){int ans= 0;num[0]= -1;for( int i= 1; i<= n; ++i ){scanf( "%d", &num[i] );}printf( "Sums of %d:\n", t );DFS( 0, 0, 0, ans );if( !ans ){puts( "NONE" );}}return 0; }

轉載于:https://www.cnblogs.com/Lyush/archive/2011/08/12/2135939.html

總結

以上是生活随笔為你收集整理的HDU-1258 Sum It Up DFS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。