A simple and fast solution in Golang by leveraing the power of next permutation


  • 0
    D

    In the implementation of next permutation, we'll try to find the next lager permutation. This process will avoid duplicated permutaions naturally.

    func permuteUnique(nums []int) [][]int {
        sort.Ints(nums)
        permutes := [][]int{}
        permutes = append(permutes, makeFromSlice(nums))
        for ; nextPermutation(nums) ; {
            permutes = append(permutes, makeFromSlice(nums))
        }
        return permutes
    }
    
    func nextPermutation(nums []int)  bool{
        cnt := len(nums)
        if cnt< 2 {
            return false
        }
        start, found:= 0, false
        for i:=cnt-1;i>0;i-- {
            if nums[i] > nums[i-1] {
                found = true
                j:=cnt-1
                for ;j>i&&nums[j]<=nums[i-1];j-- {}
                nums[j],nums[i-1]=nums[i-1],nums[j]
                start = i
                break
            }
        }
        //reverse the rest 
        for i,j:=start,cnt-1;i<j;i,j=i+1,j-1 {
            nums[j],nums[i]=nums[i],nums[j]
        }
        return found
    }
    
    func makeFromSlice(slice []int) []int {
        result := make([]int, len(slice))
        copy(result, slice)
        return result
    }
    

Log in to reply
 

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