leetcode-go/oj/tencent-2019-summer/no5/building.go

package main

import "fmt"

const MOD int = 1000000009

var n, L int

func main() {
	fmt.Scan(&n, &L)
	color := make([]int, n)
	for i := range color {
		fmt.Scan(&color[i])
	}
	used := make([]bool, n)
	cnt := dfs(color, 0, 0, -1, used)
	fmt.Println(cnt)
}

func dfs(color []int, l int, cnt int, hi int, used []bool) int {
	if n-l+cnt < L || L < cnt {
		return 0
	}
	if l == n {
		if cnt == L {
			return 1
		}
		return 0
	}
	res := 0
	for i := 0; i < n; i++ {
		if used[i] {
			continue
		}
		used[i] = true
		if hi == -1 {
			res += dfs(color, l+1, cnt+1, i, used)
		} else if hi < i {
			if color[hi] != color[i] {
				res += dfs(color, l+1, cnt+1, i, used)
			} else {
				res += dfs(color, l+1, cnt, i, used)
			}
		} else {
			res += dfs(color, l+1, cnt, hi, used)
		}
		used[i] = false
	}
	return res
}