algorithm - 查找具有重复项的数组的排列。为什么在递归中按值传递(C++实现)

Question

有不同的方法可以找到具有重复项的整数数组的所有排列。这里只讲递归的方法，不使用额外的“visited[]”数组。

正确的做法是:

    void helper(vector<vector<int>>& ans, vector<int> nums, int pos) {
        if(pos == nums.size()-1) {
            ans.push_back(nums);
            return;
        }
        for(int i = pos; i < nums.size(); i++) {
            if(i == pos || nums[i] != nums[pos]) {
                swap(nums[i], nums[pos]);
                helper(ans, nums, pos+1);
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        helper(ans, nums, 0);
        return ans;
    }

我不太清楚为什么它将 nums[] 作为副本传递给递归函数。所以我环顾四周geeks for geeks ，它说“这个想法是将第一个字符固定在第一个索引处并递归调用其他后续索引”。我在想我可以修复第一个字符，然后通过将 nums[] 作为引用传递并在递归完成时“交换回来”来递归调用其他后续索引(如下所示)。但不幸的是它没有用。

void helper(vector<vector<int>>& ans, vector<int>& nums, int pos) {
    if(pos == nums.size()-1) {
        ans.push_back(nums);
        return;
    }
    for(int i = pos; i < nums.size(); i++) {
        if(i == pos || nums[i] != nums[i-1]) {
            swap(nums[i], nums[pos]);
            helper(ans, nums, pos+1);
            swap(nums[i], nums[pos]);
        }
    }
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> ans;
    sort(nums.begin(), nums.end());
    helper(ans, nums, 0);
    return ans;
}

我想知道将 nums[] 作为引用传递给递归时有什么问题？为什么通过复制将 nums[] 传递给递归是正确的？

Answer 1

我想我找到了原因。按值传递和按引用传递给出了两种完全不同的算法。要明白这一点。让我们首先注意两个重要的观察结果:

1. 我们做的第一件事就是对数组进行排序，为什么？因为我们希望所有排列都按“下一个排列”顺序访问，即 123、132、213、231、312、321。这样就不会有重复。

2. 下一个递归的子问题也保持了排序的属性。让我们用一个例子来说明这一点。输入 nums = [1,2,2,3] 传值递归，pos = 0,

   i = 0: 子问题是 [2,2,3],

   i = 1: 子问题是 [1,2,3],

   i = 2:跳过，

   i = 3 子问题是 [1,2,2]。

这一层递归的所有子问题都是SORTED。但是如果 [1,2,2,3] 通过引用传递，则子问题不会排序，因此您不能回复“下一个排列”方法来为您提供非重复排列。

如果您仍然感到困惑，请花一些时间阅读此讨论: https://discuss.leetcode.com/topic/8831/a-simple-c-solution-in-only-20-lines/28?page=2