46/47-全排列

LeetCode

发布日期: 2021-06-26

LeetCode 46. Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

method: 回溯

子树去重

因为下一个for循环还是要从头开始，所以不需要index，跟组合问题不一样
因为用过的元素不能再用，所以在每一棵子树上维护一个used数组，保证用过的数不能再用

因为从头开始遍历，所以就会碰到刚才取过的元素，可以用used数组去重，这种重复是因为每次都要从头开始遍历，所以用used将用过的index标记就可以了

vector<vector<int>> ret;
vector<int> path;
void dfs(vector<int>& nums, vector<bool>& used) {
    if (path.size() == nums.size()) {
        ret.push_back(path);
        return;
    }
    for (int i = 0; i < nums.size(); ++i) {
        if (used[i]) continue;  // 用过了就不能再用了
        used[i] = true;
        path.push_back(nums[i]);
        dfs(nums, used);
        path.pop_back();
        used[i] = false;
    }
}
vector<vector<int>> permute(vector<int>& nums) {
    vector<bool> used(nums.size(), false);
    dfs(nums, used);
    return ret;
}

LeetCode 47. Permutations II

LeetCode-47

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

method

集合里面的数字是有重复的，如果直接用46题的方法，就会出现2个{1,1,2}的结果，所以要再加一个去重

重复的element不能使用，本质上是同一个树杈的去重，可以用两种方式去重：

1.排序+比较i>0 && nums[i] == nums[i-1]
2.哈希表，这里不用排序，因为{1,2}和{2,1}都会构成正确的结果{1,2,2}和{2,1,2}

所以子树和树杈都要去重

used数组负责同一颗子树上的去重
hash哈希表负责同一树杈上的去重，因为数组元素在[-10,10]之间，就直接用数组当哈希表

vector<vector<int>> ret;
vector<int> path;
void dfs(vector<int>& nums, vector<bool>& used) {
    if (path.size() == nums.size()) {
        ret.push_back(path);
        return;
    }
    int hash[21] = {0};     // 树杈去重
    for (int i = 0; i < nums.size(); ++i) {
        if (hash[nums[i] + 10] || used[i]) continue;
        hash[nums[i] + 10] = 1;     // 标记某个值已经使用过
        path.push_back(nums[i]);
        used[i] = true;
        dfs(nums, used);
        used[i] = false;
        path.pop_back();
    }
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
    vector<bool> used(nums.size(), false);
    dfs(nums, used);
    return ret;
}

可以只用一个used

不过要先排序，让相同的元素在一起
在上面的全排列问题中，used数组用于同一子树的去重，但是在同一树层，如果两个元素相同，并且前一个元素的used[i-1]=false，说明前一个元素跟当前元素处在同一层，当前元素就不能再用了，所以也起到了同一树杈去重的功能；如果used[i-1]=true，说明前面那个元素是在之前层被用的，跟当前元素不在同一层，所以当前元素可以用

vector<vector<int>> ret;
vector<int> path;
void dfs(vector<int>& nums, vector<bool>& used) {
    if (path.size() == nums.size()) {
        ret.push_back(path);
        return;
    }
    for (int i = 0; i < nums.size(); ++i) {
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
            continue;   // number去重
        if (used[i]) continue;  // index去重
        path.push_back(nums[i]);
        used[i] = true;
        dfs(nums, used);
        used[i] = false;
        path.pop_back();
    }
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<bool> used(nums.size(), false);
    dfs(nums, used);
    return ret;
}