leetcode-go/leetcode/medium/377.combination-sum-iv.go

var empty struct{} = struct{}{}

func combinationSum4(nums []int, target int) int {
	// res := make(map[string]struct{})
	// dfs(nums, target, []int{}, &res)
	// return len(res)
	n := len(nums)
	if n == 0 {
		return 0
	}
	sort.Ints(nums)
	dp := make([]int, target+1)
	dp[0] = 1
	for i := 1; i <= target; i++ {
		for _, val := range nums {
			if i < val {
				break
			}
			dp[i] += dp[i-val]
		}
	}
	return dp[target]
}

func dfs(nums []int, target int, pre []int, res *map[string]struct{}) {
	if target < 0 {
		return
	} else if target == 0 {
		(*res)[ints2str(pre)] = empty
		return
	}
	for _, i := range nums {
		dfs(nums, target-i, append(pre, i), res)
	}
}

func ints2str(nums []int) string {
	str := make([]string, len(nums))
	for i, v := range nums {
		str[i] = strconv.Itoa(v)
	}
	return strings.Join(str, ",")
}