package list

import (
	"sort"
)

// Problem Definition: https://leetcode.cn/problems/subsets/
func subsets(nums []int) [][]int {
	var ret [][]int
	var track []int
	var backtrack func(s int)
	backtrack = func(s int) {

		tmp := make([]int, len(track))
		_ = copy(tmp, track)
		ret = append(ret, tmp)

		for i := s; i < len(nums); i++ {
			track = append(track, nums[i])
			backtrack(i + 1)
			track = track[:len(track)-1]
		}
	}

	backtrack(0)

	return ret
}

// from the sangfor's interview test
func subsets2(n int) int {
	track := []int{0}
	cnt := 0
	var backtrack func(s int)
	backtrack = func(s int) {
		sz := len(track)

		if sz >= 2 {
			a, b := track[sz-2], track[sz-1]
			if b-a > 2 {
				return
			}
		}

		if n-track[sz-1] <= 2 {
			cnt++
		}

		for i := s; i < n; i++ {
			track = append(track, i)
			backtrack(i + 1)
			track = track[:len(track)-1]
		}
	}

	backtrack(1)

	return cnt
}

func combine(n, k int) [][]int {
	var track []int
	var ret [][]int
	var backtrack func(s int)
	backtrack = func(s int) {
		if len(track) == k {
			tmp := make([]int, k)
			_ = copy(tmp, track)
			ret = append(ret, tmp)
			return
		}

		for i := s; i <= n; i++ {
			track = append(track, i)
			backtrack(i + 1)
			track = track[:len(track)-1]
		}
	}

	backtrack(1)
	return ret
}

func subsetWithDup(nums []int) (ret [][]int) {
	sort.Ints(nums)
	var track []int

	var backtrack func(s int)
	backtrack = func(s int) {
		tmp := make([]int, len(track))
		copy(tmp, track)
		ret = append(ret, tmp)

		for i := s; i < len(nums); i++ {
			if i > s && nums[i] == nums[i-1] {
				continue
			}

			track = append(track, nums[i])
			backtrack(i + 1)
			track = track[:len(track)-1]
		}
	}

	backtrack(0)

	return
}

// Problem Definition: https://www.nowcoder.com/practice/75e6cd5b85ab41c6a7c43359a74e869a?tpId=117&tqId=37742&rp=1

func combinationSum(nums []int, target int) [][]int {
	var cnt int
	var track []int
	var ret [][]int
	var backtrack func(s int)
	backtrack = func(s int) {
		if cnt == target {
			tmp := make([]int, len(track))
			copy(tmp, track)
			ret = append(ret, tmp)
			return
		} else if cnt > target {
			return
		}

		for i := s; i < len(nums); i++ {
			if i > s && nums[i] == nums[i-1] {
				continue
			}

			track = append(track, nums[i])
			cnt += nums[i]
			backtrack(i + 1)
			track = track[:len(track)-1]
			cnt -= nums[i]
		}
	}

	backtrack(0)
	return ret
}