func generateParenthesis(n int) []string {
    if n == 1 {
        return []string{"()"}
    }
    
    // ["()"]
    // ["(())", "()()"]
    // ["((()))","(()())","(())()","()(())","()()()"]
    
    set := make(map[string]struct{})
    next := generateParenthesis(n-1)
    parenthesis := "()"

    for _, p := range next {
        for i := 0; i < len(p); i++ {
            comb := p[0:i+1] + parenthesis + p[i+1:]
            set[comb] = struct{}{}
        }
    }
  
    results := make([]string, 0, len(set))
    for p := range set {
        results = append(results, p)
    }
    return results
}

func permute(nums []int) [][]int {
    return dfs(nums, []int{})
}
    
func dfs(nums []int, path []int) [][]int {
    res := [][]int{}
    if len(nums) == 0 {
        tempPath := make([]int, len(path))
        copy(tempPath, path)
        res = append(res, tempPath)
    }
    for i := 0; i < len(nums); i++ {
        tempPath := make([]int, len(path))
        copy(tempPath, path)
        tempPath = append(tempPath, nums[i])
        tempNums := make([]int, len(nums))
        copy(tempNums, nums)
        tempNums = append(tempNums[:i], tempNums[i+1:]...)
        res = append(res, dfs(tempNums, tempPath)...)
    }
    return res
}

var res [][]int

func permute(nums []int) [][]int {
    res = [][]int{}
    dfs(nums, []int{})
    return res
}
    
func dfs(nums []int, path []int) {
    if len(nums) == 0 {
        tempPath := make([]int, len(path))
        copy(tempPath, path)
        res = append(res, tempPath)
    }
    for i := 0; i < len(nums); i++ {
    cur := nums[i]
    path = append(path,cur)
    nums = append(nums[:i],nums[i+1:]...)//直接使用切片
    dfs(nums,path)
    nums = append(nums[:i],append([]int{cur},nums[i:]...)...)//回溯的时候切片也要复原，元素位置不能变
    path = path[:len(path)-1]
    }
}

var res [][]int
var tar int
var path []int
var can []int

func combinationSum2(candidates []int, target int) [][]int {
    path = []int{}
    res = [][]int{}
    tar = target
    sort.Ints(candidates)
    used := make([]bool, len(candidates))
    can = candidates
    backtrack(0, 0, used)
    return res
}

func backtrack(sum, startIndex int, used []bool) {
    if sum == tar {
        cpy := make([]int, len(path))
        copy(cpy, path)
        res = append(res, cpy)
    }
    
    for i := startIndex; i < len(can) && sum + can[i] <= tar; i++ {
        // Skip used
        if (i > 0 && can[i] == can[i - 1] && used[i - 1] == false) {
            continue
        }
        sum += can[i]
        path = append(path, can[i])
        used[i] = true
        backtrack(sum, i + 1, used)
        used[i] = false
        sum -= can[i]
        path = path[:len(path) - 1]
    }
}

var res [][]int
var tar int
var path []int
var can []int

func combinationSum(candidates []int, target int) [][]int {
    path = []int{}
    res = [][]int{}
    tar = target
    sort.Ints(candidates)
    can = candidates
    backtrack(0, 0)
    return res
}

func backtrack(sum, startIndex int) {
    if sum == tar {
        cpy := make([]int, len(path))
        copy(cpy, path)
        res = append(res, cpy)
    }
    
    for i := startIndex; i < len(can) && sum + can[i] <= tar; i++ {
        sum += can[i]
        path = append(path, can[i])
        backtrack(sum, i)
        sum -= can[i]
        path = path[:len(path) - 1]
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func generateTrees(n int) []*TreeNode {
    if n == 0 {
        return []*TreeNode{}
    }
    return traverse(1, n)
}

func traverse(start, end int) []*TreeNode {
    // This is necessary.
    if start > end {
        return []*TreeNode{nil}
    }
    
    trees := []*TreeNode{}
    for i := start; i <= end; i++ {
        left_trees := traverse(start, i-1)
        right_trees := traverse(i+1, end)
        
        for _, left_tree := range left_trees {
            for _, right_tree := range right_trees {
                root := &TreeNode{Val: i}
                root.Left = left_tree
                root.Right = right_tree
                trees = append(trees, root)
            }
        }
    }
    return trees
}

func diffWaysToCompute(expression string) []int {
    res := []int{}
    for i := range expression {
        if expression[i] == '+' || expression[i] == '-' || expression[i] == '*' {
            lefts := diffWaysToCompute(expression[:i])
            rights := diffWaysToCompute(expression[i+1:])
            for _, left := range lefts {
                for _, right := range rights {
                    r := 0
                    switch (expression[i]) {
                        case '+':
                            r = left + right
                        case '-':
                            r = left - right
                        case '*':
                            r = left * right
                    }
                    res = append(res, r)
                }
            }
        }
    }
    if len(res) == 0 {
        i, _ := strconv.Atoi(expression)
        res = append(res, i)
    }
    return res
}