leetcode-go/leetcode/medium/491.increasing-subsequences.go

type none struct{}

func findSubsequencesDP(nums []int) (ans [][]int) {
	dp := make([][]int, 0)
	set := make(map[string]none)
	for _, i := range nums {
		for _, a := range dp {
			if a[len(a)-1] <= i {
				arr := append(a, i)
				key := arr2str(arr)
				if _, ok := set[key]; !ok {
					dp = append(dp, arr)
					ans = append(ans, arr)
					set[key] = none{}
				}
			}
		}
		key := arr2str([]int{i})
		if _, ok := set[key]; !ok {
			dp = append(dp, []int{i})
			set[key] = none{}
		}
	}
	return
}

func arr2str(arr []int) string {
	var sb strings.Builder
	for _, i := range arr {
		sb.WriteString(strconv.Itoa(i))
		sb.WriteRune(',')
	}
	return sb.String()
}

func findSubsequencesDFS(nums []int) (ans [][]int) {
	dfs(nums, len(nums), 0, make([]int, 0), &ans)
	return
}

func dfs(nums []int, n int, s int, cur []int, ans *[][]int) {
	set := make(map[int]bool)
	for i := s; i < n; i++ {
		if l := len(cur); l != 0 && nums[i] < cur[l-1] {
			continue
		} else if _, ok := set[nums[i]]; ok {
			continue
		}
		set[nums[i]] = true
		nxt := append(cur, nums[i])
		if 2 <= len(nxt) {
			*ans = append(*ans, nxt)
		}
		dfs(nums, n, i+1, nxt, ans)
	}
}