Neovim-如何使用编辑器的神

排列型枚举I

https://www.acwing.com/problem/content/844/

$1$到$n$按照字典序输出所有排列.

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10;

int n;
bool st[N];
int path[N];

void dfs(int u) {
    if (u == n) {
        for (int i = 0; i < n; i ++) printf("%d ", path[i]);
        puts("");
        return ;
    }
    for (int i = 1; i <= n; i ++) {
        if (st[i]) continue;
        path[u] = i;
        st[i] = true;
        dfs(u + 1);
        st[i] = false;
    }
}

int main() {
    cin >> n;
    dfs(0);
    return 0;
}

同类型的题: https://leetcode.cn/problems/permutations/

给定一个不包含重复元素的数组, 输出所有可能的排列方式.

class Solution {
public:
    vector<bool> st;
    vector<int> path;
    vector<vector<int>> ans;

    vector<vector<int>> permute(vector<int>& nums) {
        int n = nums.size();
        st.resize(n);
        path.resize(n);

        dfs(nums, 0);
        return ans;
    }

    void dfs(vector<int> &nums, int u)
    {
        if (u == nums.size())
        {
            ans.push_back(path);
            return ;
        }

        for (int i = 0; i < nums.size(); i ++)
        {
            if (!st[i])
            {
                st[i] = true;
                path[u] = nums[i];
                dfs(nums, u + 1);
                st[i] = false;
            }
        }
    }
};

排列型枚举II

https://leetcode.cn/problems/permutations-ii/

https://www.acwing.com/problem/content/description/47/

给定一个可能包含重复元素的数组, 输出所有可能的排列方式.

class Solution {
public:
    vector<int> path;
    vector<vector<int>> ans;

    vector<vector<int>> permutation(vector<int>& nums) {

        int n = nums.size();
        if (n == 0) return ans;
        path.resize(n);
        sort(nums.begin(), nums.end());
        dfs(nums, 0, 0, 0);
        return ans;
    }
    /* 这个函数用来描述nums[u]放到path的哪个坑上 */
    void dfs(vector<int> &nums, int start, int state, int u) {
        if (u == nums.size()) {
            ans.push_back(path);
            return ;
        }
        if (!u || nums[u] != nums[u - 1]) start = 0;

        for (int i = start; i < nums.size(); i ++) {
            if (!(state >> i & 1)) {
                path[i] = nums[u];
                dfs(nums, i + 1, state + (1 << i), u + 1);
            }
        }
    }
};

组合型枚举I

https://www.acwing.com/problem/content/description/95/

从$1$到$n$这些数中选取$m$个, 枚举所有的选择方式, 并且按照字典序输出.

#include <iostream>
using namespace std;

const int N = 30;

int n, m;
bool st[N];


void dfs(int u, int cnt) {

    if (cnt == m) {
        for (int i = 1; i <= n; i ++)
            if (st[i]) printf("%d ", i);
        puts("");
        return ;
    }

    if (u > n) return ;

    st[u] = true;

    dfs(u + 1, cnt + 1);

    st[u] = false;

    dfs(u + 1, cnt);
}


int main() {
    cin >> n >> m;
    dfs(1, 0);
    return 0;
}

组合型枚举II

https://www.acwing.com/problem/content/1575/

给定一个长度为$n$的, 可包含重复数字的数组, 随机选取$m$个数字, 输出可能的方案.

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 30;

int n, m;
int a[N];
bool st[N];

void dfs(int u, int cnt) {
    if (cnt == m) {
        for (int i = 0; i < n; i ++) {
            if (st[i]) printf("%d ", a[i]);
        }
        puts("");
        return ;
    }

    if (u == n) return ;

      /* 枚举重复元素选择多少个 */
    int k = u;

    while (k < n && a[k] == a[u]) {
        st[k ++ ] = true;
        cnt ++;
    }

  // 重复元素全选
    dfs(k, cnt);

  // 重复元素选择若干个
    for (int i = k - 1; i >= u; i --) {
        st[i] = false;
        cnt --;
        dfs(k, cnt);
    }
}


int main() {

    cin >> n >> m;
    for (int i = 0; i < n; i ++) cin >> a[i];
    sort(a, a + n);
    dfs(0, 0);

    return 0;
}

电话号码的字母组合

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

class Solution {
public:
    vector<string> res;
    string str[10] = {
        "", "", "abc", "def",
        "ghi", "jkl", "mno",
        "pqrs", "tuv", "wxyz"
    };
    vector<string> letterCombinations(string digits) {
            if (digits.size() == 0) return res;
            dfs(digits, 0, "");
            return res;
    }
    void dfs(string &digits, int u, string path) {
        if (u == digits.size()) res.push_back(path);
        else {
            for (auto c : str[digits[u] - '0']) {
                dfs(digits, u + 1, path + c);
            } 
        }
    }
};