https://leetcode.com/problems/cracking-the-safe/

#include <iostream>
#include <limits.h>
#include <vector>
#include <string>
#include <iterator>
#include <map>
#include <queue>
#include <list>
#include <algorithm>
#include <stdio.h>
#include <set>

using namespace std;

class Solution {
    int total;
    string start;
    int digit;
    int numbers;
        
    bool DFS(set<string> &used, string &now, string &ans) 
    {
        if(used.size() == total) {
            now.erase(0, 1);
            now.push_back('0');
            if (now == start) {
                return true;
            }
        }
        for (int i = 0; i < numbers; i++) {
            string tmp(now);
            tmp.erase(0, 1);
            tmp.push_back('0' + i);
            if (used.find(tmp) == used.end()) {
                ans.push_back('0' + i);
                used.insert(tmp);
                bool done = DFS(used, tmp, ans);
                if (done) {
                    return true;
                } else {
                    used.erase(tmp);
                    ans.erase(ans.size() - 1);
                }
            }
        }
        return false;
    }

public:
    string crackSafe(int n, int k) {
        digit = n; numbers = k;
        total = 1; 
        for (int i = 0; i < n; i++)
            total *= k;
        set<string> used;
        string now;
        string ans;
        // init pattern
        for (int i = 0; i < n; i++) {
            ans.push_back('0');
            now.push_back('0');
        }
        start.assign(now);
        used.insert(now);

        DFS(used, now, ans);

        return ans;
    }
};

int main()
{
    string ans;
    Solution sol;
    ans = sol.crackSafe(2, 10);
    cout << "ans = " << ans << "\n";
    system("pause");
    return 1;
}