c++ for loop exception

user_13600505 0
Viewed 77

I am writing a backtracking algorithm, I think my writing is correct, but the output is wrong. I went to debug and found that the execution：When the program executes to this sentence in the for loop, sometimes it directly skips the following statement in the for loop.

Question is here: Permutation Sequence

I have written a debugging environment, which can be run directly.

My answer is here:

   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");
}

I’m not sure if it’s the c++ problem or mine, or it might be my algorithm，but I’ve checked it many times.

backtrace c++
1 Answers

My previous thinking was wrong,@Igor Tandetnik remended me . This problem requires a bit of mathematical skills or it will time out. Thanks for your help @john and @Igor Tandetnik. My finally code is here:

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;
    }
};

enter image description here

Assuming n = 4, k = 17, we can know that the 17th permutation is [3,4,1,2]. In order to find it, we need to do pruning at key nodes. How to judge? As shown in the figure, when we start the search, we visit the purple node "1", and notice that if we continue to visit (deep search) at this time, it is actually meaningless, because there are at most 3 from this node! =6 full permutations and combinations, and what we are looking for is the 17th, 6<17, so we prun directly; visit the purple node "2", the same thing can be seen, you need pruning at this node; visit the purple node "3" ", now that the conditions are met, 6> 5, you need to search down. (Note here that a simple counting technique is that when a node needs to be pruned, we need to update the value of k, k = k-the node corresponds to the factorial number).

Author: edward_wang

user_136005050
Related