A golang solution


  • 1
    N
    func subsets(nums []int) [][]int {
        m := make(map[int]int)
        sub := [][]int{[]int{}}
        
        for i := 0; i < len(nums) - 1; i++ {
            changed := false
            for j := 0; j < len(nums) - 1; j++ {
                if nums[j] > nums[j + 1] {
                    changed = true
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]
                }
            }
            if !changed {
                break
            } 
        }
    
        for i := 0; i < len(nums); i++ {
            m[nums[i]] = i
        }
    
        for i := 0; i < len(nums); i++ {
            t := []int{nums[i]}
            sub = append(sub, t)
            
            prev := [][]int{{nums[i]}}
            for j := 2; j <= len(nums) - i; j++ {
                var now [][]int
                for _, v := range prev {
                    for k := m[v[len(v) - 1]] + 1; k < len(nums); k++ {
                        t := make([]int, len(v) + 1)
                        copy(t, v)
                        t[len(v)] = nums[k]
                        now = append(now, t)
                    }
                }
                sub = append(sub, now...)
                prev = now
            }
        }
        return sub
    }

Log in to reply
 

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