package main

import (
	"fmt"
	"sort"
)

func combinationSum4(nums []int , target int ) (res int) {
	// 0.可能需要加入剪枝的逻辑
	sort.Ints(nums)
	trace, book := 0, make(map[int]int)
	var depth func()
	depth = func() {
		if _ , ok := book[trace] ; ok{
			res ++
			return
		}
		if trace > target {
			return
		}
		if trace == target {
			 res ++
			 return
		}
 		count := res
		for i := 0 ; i < len(nums) ; i ++ {
			trace += nums[i]
			depth()
			trace -= nums[i]
		}
		 book[trace] = res - count
	}
	depth()
	return res
}

func main() {
	fmt.Println(combinationSum4([]int{1,5,8},10))
}
// 181997601