Recursion

全排列

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {

        vector<vector<int>> ans;

        if (nums.empty()) {
            ans.push_back(vector<int>());
            return ans;
        }

        for (int i = 0; i < nums.size(); i++) {
            // must copy
            vector<int> others(nums);
            others.erase(others.begin() + i);
            // r
            auto p = permute(others);
            for (auto v: p) {
                v.insert(v.begin(), nums[i]);
                ans.push_back(v);
            }
        }

        return ans;
    }
};

全组合

回溯：

// find all combinations that sums to target
int ans = 0;
void dfs(vector<int>& v, int target, int idx, int cur) {
    if (idx == v.size()) {
        if (cur == target) ans++;
        return;
    }

    // dispatch two conditions
    dfs(v, target, idx + 1, cur); // do not use v[idx]
    dfs(v, target, idx + 1, cur + v[idx]); // use v[idx]
}

dfs(v, target, 0, 0);

迭代（更慢，且要求v.size() < 32）：

// find all combinations that sums to target
int ans = 0;
int maxm = (1 << v.size()) - 1;
for (int m = 0; m <= maxm; m++) {
    int val = 0;
    for (int i = 0; i < v.size(); i++) {
        if (m & (1 << i)) {
            val += v[i];
        }
    }
    if (val == target) ans++;
}

N皇后

class Solution {
public:
    vector<vector<string>> tostr(vector<vector<int>> ans, int n) {
        vector<vector<string>> sans;
        for (auto v : ans) {
            vector<string> sv;
            for (int x : v) {
                string s;
                for (int i=0; i<n; i++) {
                    if (i != x) s += '.';
                    else s += 'Q';
                }
                sv.push_back(s);
            }
            sans.push_back(sv);
        }
        return sans;
    }

    bool safe(vector<int> cur, int i) {
        int s = cur.size();
        for (int j=0; j<s; j++) {
            if (cur[j] == i || j - cur[j] == s - i || j + cur[j] == i + s) return false;
        }
        return true;
    }

    void solve(vector<vector<int>>& ans, vector<int> cur, int n) {
        if (cur.size() == n) {
            ans.push_back(cur);
            return;
        }
        for (int i=0; i<n; i++) {
            if (safe(cur, i)) {
                auto next = cur;
                next.push_back(i);
                solve(ans, next, n);
            }
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        vector<vector<int>> ans;
        vector<int> cur;
        solve(ans, cur, n);
        return tostr(ans, n);
    }
};