Confused by uniqueness in rearrangement

Question

Work on the problem below as a puzzle algorithm. I wrote several similar solutions (and posted one of them below), tried it, and they worked. The question is, for the string “swap (num [i], num [k]);”, how can we guarantee that we can always change the number that we have never tried before (for example, suppose we change 1 for 2 in the current iteration, the for loop, can we later change 2 back to 1 in the next iterations of the same for the cycle of the same level / level of the recursive call)? I have a confusion, since we pass num by reference, and it is very possible later (lower level / level) of recursive calls to modify the contents of the number, which leads to the fact that the numbers we have already evaluated swap back. However, I have tried and it works for all my test cases. Surprise,if the solution below is 100% correct, or happened with my test cases? :)

Below is a detailed report of the problem and the code I am debugging,

Given a set of numbers that may contain duplicates, return all possible unique permutations.

For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1] and [2,1,1]

class Solution {
public:
    void recursion(vector<int> num, int i, int j, vector<vector<int> > &res) {
        if (i == j-1) {
            res.push_back(num);
            return;
        }
        for (int k = i; k < j; k++) {
            if (i != k && num[i] == num[k]) continue;
            swap(num[i], num[k]);
            recursion(num, i+1, j, res);
        }
    }
    vector<vector<int> > permuteUnique(vector<int> &num) {
        sort(num.begin(), num.end());
        vector<vector<int> >res;
        recursion(num, 0, num.size(), res);
        return res;
    }
};

thanks in advance Lin

Answer 1

As @notmyfriend said in the comments, numactually copied every function call.
So now it comes down to:

• From all the values ​​of the array, select one so that it is the first and places it there. This is in a loop for each value once, and then recursively:
  • Of all the values ​​after the first, select it first and place it there ...

... .. , , , .. .

num , ( , ).
. 1 1 2 - , :

112, 121, 211, 112, 121  

. , (, , , ).

:

++
(normal = '&' ..).
, C-: , , , ( ). , , .

std::vector () , ( -). , ( ).
, , , ; ++ , .. , .
, , ...

Answer 2

, Java. ++, . .

Backtracking (https://en.wikipedia.org/wiki/Backtracking) hashset , , , hashset, .

input  :  [1, 1, 2]
output :  [1, 1, 2]
          [1, 2, 1]
          [2, 1, 1]

:

public class permutation {

    public static void main(String[] args) {
        permutation p = new permutation();
        p.permute(new int[] { 1, 1, 2 });
    }

    HashSet<String> set = new HashSet<String>();

    private void permute(int[] arr) {
        set.clear();
        this.permute(arr, 0, arr.length - 1);
    }

    private void permute(int[] arr, int l, int r) {
        if (l == r) {
            String key = Arrays.toString(arr);
            if (set.contains(key))
                return;
            set.add(key);
            System.out.println(key);
        } else {
            for (int i = l; i <= r; i++) {
                swap(arr, l, i);
                permute(arr, l + 1, r);
                swap(arr, i, l);
            }
        }
    }

    private void swap(int[] arr, int l, int r) {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
    }
}