suibenzhi
4/15/2018 - 5:36 AM

子集树与排列树.cpp


//子集树
void Backtrack(int t) {     //t 表示当前是树的第t层,即对集合 S 中的第 t 个元素进行判断
    if (t > n)
        output(x);          //大于S中总的元素个数 ,遍历完成 
    else
        for (int i = 0; i < = l; i++) {     // 两种可能 加入或者不加入到解集合 
            x[t] = i;
            if (Constraint(t) && Bound(t)){     //满足约数条件  
                    Backtrack(t + 1);           //对 t+1 层进行判断 
                } 
        }
}



//排列树:
void Backtrack(int t) {     //t 表示集合 S 的第 t 个元素 
    if (t > n)
        output(x);
    else
        for (int i = t; i <= n; i++) {      //第t 个元素与其后面的所有元素进行交换位置 
            swap(x[t], x[i]);
            if (constraint(t) && bound(t)){ 
                    backtrack(t + 1);
                } 
            swap(x[t], x[i]);
        }
}