C++ for 循环异常

Question

我在写一个回溯算法，我觉得我写的是对的，但是输出是错误的。去调试发现执行:当程序执行到for循环中的这一句时，有时会直接跳过for循环中的后面语句。

问题在这里: Permutation Sequence

我写了一个调试环境，可以直接运行。

我的答案在这里:

   class Solution {
 public:
  int index = 0, N, K;
  string ans;
  string getPermutation(int n, int k) {
    N = n;
    K = k;
    string str;
    backtrace(str, 0);
    return ans;
  }

  void backtrace(string &str, int start) {
    if (start == N) {
      index++;
      if (index == K) {
        ans = str;
      }
      return;
    }

    for (int i = start; i < N; i++) {
      if (index == K) {
        return;
      }

      string temp = str; //For loop to this sentence will not execute the following statement

      str += to_string(i + 1);
      backtrace(str, i + 1);
      str = temp;
    }
  }
};
int nn(int n) {
  if (n == 1) {
    return 1;
  }
  return nn(n - 1) * n;
}
int main() {
  Solution so;
  for (int i = 1; i <= nn(3); i++) {
    cout << so.getPermutation(3, i) << endl;
  }

  system("pause");
}

我不确定是c++的问题还是我的问题，也可能是我的算法问题，但是我已经检查了很多次了。

Answer 1

我之前的想法是错误的，@Igor Tandetnik 提醒我。这个问题需要一点数学技巧，否则会超时。感谢@john 和@Igor Tandetnik 的帮助。我的最终代码在这里:

class Solution {
private:
    vector<int> hash;
    vector<int> factorial;
    bool flag = true;
    void dfs(int cur, int n, int &k, string &ret, int &cnt, string path){
        if(cur == n){
            ret = path;
            flag = false;
            return;
        }
        int temp = factorial[n-cur-1];
        for(int i=0; i<n; i++){
            if(hash[i] && flag){
                if(temp < k ){
                    k = k - temp;
                    continue;
                }
                path.push_back(i+1+'0');
                hash[i] = 0;
                dfs(cur+1,n,k,ret,cnt,path);
                hash[i] = 1;
                path.pop_back();
            }
        }
    }

public:
    string getPermutation(int n, int k) {
        //calculate the factorial
        if(n == 1) return "1";
        factorial.resize(n);
        factorial[0] = 1;
        factorial[1] = 1;
        if(n > 2){
            for(int i=2; i<n; i++){
                factorial[i] = i * factorial[i-1];
            }
        }
        string ret;
        string path;
        hash.resize(n,1);
        int cnt = 0;
        dfs(0,n,k,ret,cnt,path);
        return ret;
    }
};

假设n=4，k=17，我们可以知道第17个排列是[3,4,1,2]。为了找到它，我们需要在关键节点上进行剪枝。如何判断？如图所示，当我们开始搜索时，我们访问了紫色节点“1”，注意到如果此时继续访问(深度搜索)，其实是没有意义的，因为最多有3个来自这个节点! =6个全排列组合，而我们要找的是第17个，6<17，所以我们直接剪枝；访问紫色节点“2”，同样可以看到，需要在该节点进行剪枝；访问紫色节点“3””，既然满足条件，6>5，就需要往下查找。(这里注意一个简单的计数技巧，当一个节点需要被剪枝时，我们需要更新值of k, k = k-节点对应阶乘数)。

作者:edward_wang