迭代加深dfs

每次控制序列的长度，依次加深搜索

有几个剪枝：

• 优化搜索顺序，从大往下枚举i， j这样能够让序列中的数尽快逼近n
• 对于不同i，j和可能是相等的，在枚举的时候用过的数肯定不会再被填上所以可以去重(记得回溯)

#include 
    
     #include 
     
      #include 
      
       #define INF 0x3f3f3f3fusing namespace std;typedef long long ll;inline int lowbit(int x){ return x & (-x); }inline int read(){    int X = 0, w = 0; char ch = 0;    while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }    while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();    return w ? -X : X;}inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; }inline int lcm(int a, int b){ return a / gcd(a, b) * b; }template
       
        inline T max(T x, T y, T z){ return max(max(x, y), z); }template
        
         inline T min(T x, T y, T z){ return min(min(x, y), z); }template
         
          inline A fpow(A x, B p, C yql){ A ans = 1; for(; p; p >>= 1, x = 1LL * x * x % yql)if(p & 1)ans = 1LL * x * ans % yql; return ans;}const int N = 1005;int n, a[N], depth;bool vis[N];bool dfs(int cur){ if(cur == depth + 1){ return a[depth] == n; } for(int i = cur - 1; i >= 1; i --){ for(int j = i; j >= 1; j --){ if(a[i] + a[j] > a[cur - 1] && !vis[a[i] + a[j]]){ a[cur] = a[i] + a[j]; vis[a[cur]] = true; if(dfs(cur + 1)) return true; vis[a[cur]] = false; } } } return false;}int main(){ while(scanf("%d", &n) != EOF && n){ for(int i = 1; ; i ++){ memset(vis, 0, sizeof vis); memset(a, 0, sizeof a); a[1] = 1; depth = i; if(dfs(2)){ for(int j = 1; j < depth; j ++) printf("%d ", a[j]); printf("%d\n", a[depth]); break; } } } return 0;}