题目背景
猪猪 Hanke 得到了一只鸡。
题目描述
猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有 10 种配料（芥末、孜然等），每种配料可以放 1 到 3 克，任意烤鸡的美味程度为所有配料质量之和。
现在， Hanke 想要知道，如果给你一个美味程度 n ，请输出这 10 种配料的所有搭配方案。
输入格式
一个正整数 n，表示美味程度。
输出格式
第一行，方案总数。
第二行至结束，10 个数，表示每种配料所放的质量，按字典序排列。
如果没有符合要求的方法，就只要在第一行输出一个 0。
输入输出样例
输入 #1
11
输出 #1
10
1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 1 2 1 1
1 1 1 1 1 1 2 1 1 1
1 1 1 1 1 2 1 1 1 1
1 1 1 1 2 1 1 1 1 1
1 1 1 2 1 1 1 1 1 1
1 1 2 1 1 1 1 1 1 1
1 2 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1
说明/提示
对于 100% 的数据，n≤5000。
方法一
暴力破解
import java.util.Scanner;
public class 烤鸡 {
public static void main(String[]args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int a,b,c,d,e,f,g,h,i,j,count = 0;
for(a=1;a<=3;a++) {
for(b=1;b<=3;b++) {
for(c=1;c<=3;c++) {
for(d=1;d<=3;d++) {
for(e=1;e<=3;e++) {
for(f=1;f<=3;f++) {
for(g=1;g<=3;g++) {
for(h=1;h<=3;h++) {
for(i=1;i<=3;i++) {
for(j=1;j<=3;j++) {
if(a+b+c+d+e+f+g+h+i+j==n) {
count++;
}
}
}
}
}
}
}
}
}
}
}
System.out.println(count);
for(a=1;a<=3;a++) {
for(b=1;b<=3;b++) {
for(c=1;c<=3;c++) {
for(d=1;d<=3;d++) {
for(e=1;e<=3;e++) {
for(f=1;f<=3;f++) {
for(g=1;g<=3;g++) {
for(h=1;h<=3;h++) {
for(i=1;i<=3;i++) {
for(j=1;j<=3;j++) {
if(a+b+c+d+e+f+g+h+i+j==n) {
System.out.println(a+" "+b+" "+c+" "+d+" "+e+" "+f+" "+g+" "+h+" "+i+" "+j);
}
}
}
}
}
}
}
}
}
}
}
}
}
方法二
dfs
此题需要先输出方案，故每个方案需要保存在一个ans数组中；一维为第几种方案，二维为方案内容；
在dfs中，两个参数，层数u，目前的调料质量之和sum；
这种方法我目前还没学到，先收藏起来，以后再分析
import java.util.Scanner;
public class Main {
static int n;
static int[][] ans = new int[100000][15];//一维为第几种方案，二维为方案内容
static int[] temp = new int[15];//保存临时方案
static int cnt = 0;//方案总数
static void dfs(int u, int sum) {
if (u == 10) {//搜索到底，满足输出条件，保存方案
if (sum == n) {
for (int i = 0; i < 10; i++)
ans[cnt][i] = temp[i];
cnt++;
}
return;//搜索到底，回溯
}
for (int i = 1; i <= 3; i++) {//每一层可选的
temp[u] = i;//当前的调料放的量
dfs(u + 1, sum + i);
temp[u]=0;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
dfs(0, 0);//从第一层搜起,质量和为0
System.out.println(cnt);
if (cnt != 0)
for (int i = 0; i < cnt; i++) {
for (int j = 0; j < 10; j++)
System.out.print(ans[i][j]+" ");
System.out.println();
}
}
}
