/*
 * @lc app=leetcode.cn id=77 lang=golang
 *
 * [77] 组合
 */

// @lc code=start
func combine(n int, k int) (res [][]int) {
	if k == 1{
		for i := n; i > 0 ; i-- {
			res = append(res, []int{i})
		}
		return 
	}
	for i := n; i >= k ; i-- {
		temp := combine(i-1, k-1)
		for _, v := range temp {
			res = append(res, append([]int{i}, v...))
		}
	}
	return 
}

// func combine(n int, k int) (res [][]int) {
// 	if k == 1{
// 		for i := 1; i <= n ; i++ {
// 			res = append(res, []int{i})
// 		}
// 		return 
// 	}
// 	for i := 1; i <= n ; i++ {
// 		preTemp := make([]int,0)
// 		j := 0
// 		for ; j < k - 1; j++ {
// 			preTemp = append(preTemp, i+j)
// 		}
// 		for z := i + j; z <= n; z++ {
// 			res = append(res, append(preTemp, z))
// 		}
// 	}
// 	return 
// }


// @lc code=end

2 12 
3 12 13 23 
4 12 13 14 23 24 34 
5 12 13 14 15 23 24 25 34 35 45
6 12 13 14 15 16 23 24 25 26 34 35 36 45 46 56 

2  3  6 10 15 

1
2 + 1
3 + 2 + 1
4 + 3 + 2 + 1
5 + 4 + 3 + 2 + 1

3 123 
4 123 124 134 234 
5 123 124 125 134 135 234 235 245 345  
6 123 124 125 126 234 235 236 345 346 456 

2 3 6 10 

1
3 + 1
3 + 2 + 1
4 + 3 + 2 + 1