Easy solution using code in nextPermutation (can be used in Permutations II without modification)


  • 15

    Well, have you solved the nextPermutation problem? If so, your code can be used in this problem. The idea is fairly simple:

    1. add nums to res;
    2. generate the next permutation of nums using nextPermutation(), and add it to res;
    3. repeat 2 until the next permutation of nums returns to the original configuration.

    The code is as follows.

    A final note, the following code can be applied to the problem of Permutations II without any modification since the cases of duplicates have already been handled in nextPermutation(). If you want to learn more about nextPermutation(), please visit this solution.

        bool nextPermutation(vector<int>& nums) {
            int k = -1;
            for (int i = nums.size() - 2; i >= 0; i--) {
                if (nums[i] < nums[i + 1]) {
                    k = i;
                    break;
                }
            }
            if (k == -1) {
                reverse(nums.begin(), nums.end());
                return false;
            }
            int l = -1;
            for (int i = nums.size() - 1; i > k; i--) {
                if (nums[i] > nums[k]) {
                    l = i;
                    break;
                }
            }
            swap(nums[k], nums[l]);
            reverse(nums.begin() + k + 1, nums.end());
            return true;
        }
        vector<vector<int>> permute(vector<int>& nums) {
            vector<vector<int> > res;
            sort(nums.begin(), nums.end());
            res.push_back(nums);
            while (nextPermutation(nums))
                res.push_back(nums);
            return res;
        }
    

  • 1
    D

    @jianchao.li.fighter What is the time complexity for this code?


  • 0
    P

    Hello Sir,

    This is definitely a good solution. Could you please tell us the time complexity of this algorithm.

    I think it should be (n!*n) as there are n! possible permutations and finding next permutation takes O(n). Please correct me if I am wrong.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.