Today, I brushed offer and wrote offer 38. I found that I didn’t have a complete grasp of the arrangement of strings.

In fact in a few months ago to arrange for the whole problem specially wrote a blog, with the deep wide search and search the two methods, felt the whole arrangement for his already is not a problem, the result when doing full arrangement related to the topic today does not start in the first time to write, but give me some time, I am sure that you can write).

In the algorithm class of last semester, I talked about the problem of full permutation. When I saw the solution in the book, I found that my previous code was terrible in both time and space, so I decided to write a blog about full permutation to consolidate it.

Previous full permutation blog: Deep search for full permutation, extensive search for full permutation.

Leetcode 46, leetcode 47, leetcode 47 Full permutation II.

Full permutation of non-repeating elements

Consider arrays [1,2,3,4], as shown in the figure above, where each element can be used as a starting element for a permutation, and the solution to the whole problem can be divided into four classes. The solution set of each class is a combination of the initial elements of the class and all permutations of the remaining elements.

class Solution {
public:
    vector<vector<int>> result;
    vector<int> nums;

    void help(int begin, int end) {
        if (begin == end) {
            result.push_back(nums);
        }
        for (int i = begin; i < end; ++i) {
            swap(nums[begin], nums[i]);
            help(begin+1, end);
            swap(nums[begin], nums[i]);
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        this->nums = nums;
        help(0, nums.size());
        returnresult; }};Copy the code

In the above code, each element is iterated over, swapped with the starting element of the array, and then the remaining elements are sorted through help. When the problem size is 0, numS is in a sorted state and merged into the result result set.

There are full permutations of repeating elements

Consider the array [1,1,3,4], as shown in the figure above. The entire result set should be divided into 3 classes instead of 4. If it is 4, where both classes start with 1, then the result set will have the same arrangement. The difficulty of the problem lies in how to remove the weight. My solution to this problem is different from the solution to the official problem of Leetcode (I think my solution is better than the solution of the problem). My solution inherits the code of full arrangement of non-repeating elements and uses the Visited array to duplicate.

By the picture above is not hard to think of, as long as with appropriate filter condition in the process of traversing, let each can and starting element exchange elements is not repeat can reach to each other, the purpose of using visited here [n] = 1 equals to n elements has been with starting element, note here instead the subscript n element value.

class Solution {
public:
    vector<vector<int>> result;
    vector<int> nums;

    void help(int begin, int end) {
        if (begin == end) {
            result.push_back(nums);
        }
        vector<int> visited(21.0);
        for (int i = begin; i < end; ++i) {
            if (visited[nums[i]+10]) continue;
            visited[nums[i]+10] = 1;
            swap(nums[begin], nums[i]);
            help(begin+1, end);
            swap(nums[begin], nums[i]);
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        this->nums = nums;
        help(0, nums.size());
        returnresult; }};Copy the code

-10 <= nums[I] <= 10, so vector

visited(21, 0); , requires a conversion between [-10,10] and [0,20] when marking.

Until I got it right, I fell into the trap of trying to de-duplicate the starting element without marking the array.

sort(nums.begin(), nums.end());
for (int i = begin; i < end; ++i) {
    if (i > 0 && nums[i] == nums[i- 1]) {
        continue; }}Copy the code

The above code does make sure that each loop is a different element to swap with the original element, but the remaining elements after the swap are no longer ordered, and the help function does require order for the permutation interval. I also thought about using temporary arrays as arguments, but not only is the space expensive, And it’s not as much code or as difficult to understand as using tag arrays.