package main

import (
	"fmt"
	"sort"
)

// 本质上就是背包问题，都是用几个元素合成一个元素的组合问题，可以使用dp，但非常规递推dp，而是组合dp,所以复杂度是len(nums) * target
// 回溯和dp解的前提条件都是排序,这样才具备剪枝的完备性
func combinationSum4(nums []int , target int )  int {
	sort.Ints(nums)
	dp := make([]int,target + 1 , target + 1)
	dp[0] = 1
	for i := 1 ; i <= target ; i ++ {
		for j := 0 ; j < len(nums) ; j ++ {
			if idx := i - nums[j] ; idx >= 0 {
				dp[i] += dp[idx]
			}else {
				break
			}
		}
	}
	return dp[target]
}

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