计算机算法设计与分析学习笔记

电子工业出版社，第五版，第五章回溯算法

解空间树为排列树的回溯算法的非递归实现，待完善

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param S int整型vector
     * @return int整型vector<vector<>>
     */
#define MAX 10
    int n = 0;
    int x[MAX] = {0}; //可行解
    string h;//t等于i时的可选值
    //当前扩展结点的未搜索过的子树的起始编号
    int f(int n, int t) {
        return 0;
    }
    //当前扩展结点的未搜索过的子树的终止编号
    int g(int n, int t) {
        return 1;
    }
    //x[1:t]部分可行解满足的约束，当t=n是得到问题的可行解
    int Constraint(int t) {
        return 1;
    }
    //x[1:t]部分可行解的限界函数，当t=n时得倒问题的可行解
    int Bound(int t) {
        return 1;
    }
    vector<vector<int>>ans;
    //输出处理函数
    void Output(int x[]) {
        vector<int>tmp;
        for (int i = 1; i <= n; i++) {
            tmp.push_back(x[i]);
        }
        ans.push_back(tmp);
    }

    void BackTrack(int t) {

        if (t > n) {//回溯终止
            Output(x);
        } else {
            //对当前结点进行扩展
            for (int i = f(n, t); i <= g(n, t); i++) {
                x[t] = i;
                //检查约束和限界
                //约束函数用于选取满足条件的一个解
                //而界限函数用于剪除不可能存在解的节点
                if (Constraint(t) && Bound(t))
                    BackTrack(t + 1);
            }

        }
    }
    vector<vector<int> > subsets(vector<int>& S) {
        // write code here
        vector < vector<int>> ret;
        n = S.size();
        vector<int> ans_sub, ret_sub;
        //h, x;
        BackTrack(1);//调用回溯算法
        for (int i = 0; i < ans.size(); i++) {
            ans_sub.clear();
            ret_sub.clear();
            ans_sub = ans[i];
            for (int j = 0; j < n; j++) {
                if (ans_sub[j] == 1)ret_sub.push_back(S[j]);
            }
            ret.push_back(ret_sub);

        }
        return ret;
    }
};

使用教材中的算法模版，算法运行超时。待修改

#include <any>
#include <cstring>
#include <mutex>
#include <string>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串vector
     */
    int n = 0;
    string x;//可行解
    string h;
    int f(int n, int t) {
        return t;
    }
    int g(int n, int t) {
        return n;
    }
    int Constraint(int t) {

        return 1;
    }
    int Bound(int t, vector<string>BackTackedList) {
        int flag = 1;
        //剪掉部分枝叶
        if (BackTackedList.size() == 1)return 1;
        for (int j = 0; j < BackTackedList.size() - 1; j++) {
            if (BackTackedList[j] == *BackTackedList.end()) {
                return 0;
                // break;
            }

        }
        return 1;
    }
    set<string>ans;
    set<string> Output(string x) {
        ans.insert(x.substr(1, x.size() - 1));
        return ans;
    }
    void BackTrack(int t) {
        if (t > n) {
            Output(x);
        } else {
            for (int i = f(n, t); i <= g(n, t); i++) {
                // x[t] = h[i];
                swap(x[t], x[i]);
                vector<string> BackTackedList;
                BackTackedList.push_back(x);
                //生成已经回溯过的结点列表
                if (Constraint(t) && Bound(t,BackTackedList))
                    BackTrack(t + 1);
                swap(x[t], x[i]);
            }

        }
    }
    vector<string> Permutation(string str) {
        // write code here
        n = str.length();
        h = str, x = ' ' + str;
        BackTrack(1);
        vector<string>  ret;
        for (auto it = ans.begin(); it != ans.end(); it++) {
            ret.push_back(*it);
        }
        return ret;
    }
};