配列が重複している順列を見つける。再帰（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

私は理由を見つけたと思う。値渡しと参照渡しの2つの全く異なるアルゴリズムがあります。それを理解する。最初に2つの重要な観察を書きましょう：

1. まず、アレイを並べ替えることです、なぜですか？ 123、132、213、231、312、321の順番ですべての並べ替えを参照する必要があるため、重複はありません。

2. 次の再帰のサブ問題はソートされたプロパティも維持しました。例を使ってこれを説明しましょう。 入力NUMS POS = 0と再帰に値による= [1,2,2,3]パッシング、

   I = 0：サブ問題は、[2,2,3-]、

   I = 1です。サブ問題[1,2,3]、

   I = 2である：[1,2,2] I = 3の部分問題は、

   をスキップ。

このレベルの再帰のサブ問題はすべてSORTEDです。 [1,2,2,3]が参照渡しされた場合、サブ問題はソートされないため、「次の順列」メソッドで返信して、重複しない順列を返すことはできません。あなたはまだ混乱している場合は

は、この議論を通読するためにいくつかの時間がかかるしてください： https://discuss.leetcode.com/topic/8831/a-simple-c-solution-in-only-20-lines/28?page=2