Who can tell me how to slove this in Golang by using backtrack ?


  • 0
    N

    Here is my solution. I think it will be a normal backtrack solution if I use c++. But by using golang it will soon get TLE with the case
    [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
    I think the problem maybe is the answer's size is too large so the program need to use append so frequently. So once the cap of the slice is not enough, the append function need to carry on a copy action.
    And other problem may be return type, in golang, return the type [][]int means when I try to add a answer to the slice, I need to copy the answer. If not, all the answer in the list will be the same as they are point to the same array.
    I think this is why this solution got TLE. But I do not know my guess is right and how to solve it.
    So can someone help me pls~!

    var ret [][]int
    
    func help(nums, now []int, idx int, str [15]int, strLen int, m map[[15]int]bool) {
    	if len(now) >= 2 {
    		tmp := make([]int, len(now))
    		copy(tmp, now)
    		ret = append(ret, tmp)
    	}
    
    	for i := idx; i < len(nums); i++ {
    		if len(now) != 0 && nums[i] < now[len(now)-1] {
    			continue
    		}
    
    		str[strLen] = nums[i]
    		_, ok := m[str]
    		if ok {
    			continue
    		}
    		m[str] = true
    		now = append(now, nums[i])
    		help(nums, now, i+1, str, strLen+1, m)
    		now = now[:len(now)-1]
    		str[strLen] = -111
    	}
    }
    
    func findSubsequences(nums []int) [][]int {
    	ret = [][]int{}
    	t := make([]int, 0, len(nums)+1)
    	indexList := [15]int{}
    	for i := 0; i < 15; i++ {
    		indexList[i] = -111
    	}
    	m := make(map[[15]int]bool)
    	help(nums, t, 0, indexList, 0, m)
    	return ret
    }
    

  • 0

    same problem.~


Log in to reply
 

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