LeetCode: Permutations II

Given a collection of numbers that might 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].

---

Here we can use the same idea as the previous problem. Additionally, we need to check whether we need to swap to avoid duplicate cases.

C++ Code:

/*
 * func: no_swap
 * goal: to check if swap is necessary for the current pair
 * @param start_position: left swap element
 * @param i: right swap element
 * @param num: integers vector
 * return: true or false
 */
bool no_swap(size_t start_position, size_t i, const vector<int>& num){
    for(size_t iter = start_position; iter < i; ++iter){
        if(num[iter] == num[i]){
            return true;
        }
    }
    return false;
}

/*
 * func: permutation_ii_helper
 * goal: helper function for creating permutations
 * @param start_position: start position for each swap
 * @param num: integer vector
 * @param result: final result vector
 * return:
 */
void permutation_ii_helper(size_t start_position, vector<int> &num, vector<vector<int> > &result){
    if(start_position == num.size()-1){
        result.emplace_back(num);
        return;
    }
    for(size_t i = start_position; i < num.size(); ++i){
        if(no_swap(start_position, i, num)){
            continue;
        }
        swap(num[start_position], num[i]);
        permutation_ii_helper(start_position+1, num, result);
        swap(num[start_position], num[i]);
    }
}

/*
 * func: permutation_ii
 * goal: generate all permutations of the given list without duplicates
 * @param num: integers vector
 * return: all possible permutations
 */
vector<vector<int> > permutation_ii(vector<int> &num){
    vector<vector<int> > result;
    permutation_ii_helper(0, num, result);
    return result;
}

For Python, here I implemented it with the help of function next_permutation from previous problem.

# func: Implement next permutation, which rearranges numbers into the
#       lexicographically next greater permutation of numbers.
# @param num: input number list
# @return: return next permutation
def next_permutation(num):
    if len(num) <= 1:
        return num

    #Find the largest index where num[index] < num[index+1]
    index = len(num)-2
    while index >= 0:
        if num[index] < num[index+1]:
            break
        else:
            index -= 1

    #If there doesn't exist that index, reverse the whole list
    if index < 0:
        return num[::-1]

    #Find the largest index' that num[index'] > num[index]
    index_g = len(num)-1
    while index_g > index:
        if num[index_g] > num[index]:
            break
        else:
            index_g -= 1

    #Swap index_g and index
    tmp = num[index]
    num[index] = num[index_g]
    num[index_g] = tmp

    #Reverse from index + 1 to the end
    num[index+1:] = reversed(num[index+1:])

    return num

# func: generate all possible permutations without duplicates
# @param num: a list of integer
# @return: a list of permutations
def permutation_ii(num):
    num.sort()
    result = []
    result.append(num)
    x = next_permutation(num[:])
    while x != num:
        result.append(x)
        x = next_permutation(x[:])

    return result