题目
骰子的点数是1 到 6，当有n个骰子的时候，其点数和等于m的数量
如当n = 4 m = 23时候 有下面四种：
5666
6566
6656
6665
解题
深度优先，开始第一感觉很复杂，然后就没有写，后来在最后几分钟写了出来，但是提交发现以为有相同的情况，用TreeSet存放符合条件的种类，发现还是不对，刚在本地测试发现下面的问题
当求 2 个数的和是 6的时候，输出结果是 15 、24、33、42、51、6，当两个数的和是5的时候输出：14、41、23、32、5 ，是这种情况我误以为是由于出现重复数据，最后时间不对，也没有再改
但是对于自己能做到这里还是比较满意的。
对于出现长度不到n，和等于m的情况，只有利用其长度了。应该有其他的好方法
import java.util.Iterator;
import java.util.TreeSet;
import java.util.Scanner;
public class Main{
static int count;
static TreeSet<String> set;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
count = 0;
set = new TreeSet<String>();
int n = in.nextInt();
int m = in.nextInt();
String s = "";
dfs(n,n,m,s);
System.out.println(count+"\t"+set.size());
Iterator it = set.iterator();
while(it.hasNext()){
String tmp = (String)it.next();
System.out.print(tmp+"\t");
}
}
in.close();
}
public static void dfs(int N,int n,int m,String s){
if(n<0)
return;
if(n==0 && m==0 && s.length() == N){
//System.out.println(s);
set.add(s);
count++;
return;
}
while((n--)>0){
for(int i =1;i<=6;i++){
s+=i+"";
dfs( N,n,m-i,s);
s = s.substring(0,s.length()-1);
}
}
}
}
那么少的程序，傻子都能写出来了。。。
提交的程序少了一行：
s = s.substring(0,s.length()-1);
这样对个数竟然没有影响（虽然可能输出只有一个数就等于m的情况）
原因是判断少了
s.length() == N
但是为什么不加判断是否等于N时候为什么可以输出一个数的和等于m的情况？可能是while循环中用到了 n--的情况
我的这个方法还是不好，用N判断长度，太冗余，利用TreeSet增加了空间复杂度。
上面可以发现我定义count最后的值和TreeSet的大小是一样的，所有可以不用TreeSet。
更新如下
import java.util.Scanner;
public class Main{
static int count;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
count = 0;
int n = in.nextInt();
int m = in.nextInt();
String s = "";
dfs(n,n,m,s);
System.out.println(count);
}
in.close();
}
public static void dfs(int N,int n,int m,String s){
if(n<0)
return;
if(n==0 && m==0&& s.length() == N){
count++;
return;
}
while((n--)>0){
for(int i =1;i<=6;i++){
s+=i+"";
dfs( N,n,m-i,s);
s = s.substring(0,s.length()-1);
}
}
}
}
在第一次写的时候也没有TreeSet 在输入2 6多出一个结果的时候才用TreeSet，结果还是没有找到主要问题，但是网易测试用例要自己输入，一个坑，不知道自己的用例是否太少。
测出结果
1 6
1 1
6
2 6
5 5
15 24 33 42 51
4 23
4 4
5666 6566 6656 6665
5 25
126 126
16666 25666 26566 26656 26665 34666 35566 35656 35665 36466 36556 36565 36646 36655 36664 43666 44566 44656 44665 45466 45556 45565 45646 45655 45664 46366 46456 46465 46546 46555 46564 46636 46645 46654 46663 52666 53566 53656 53665 54466 54556 54565 54646 54655 54664 55366 55456 55465 55546 55555 55564 55636 55645 55654 55663 56266 56356 56365 56446 56455 56464 56536 56545 56554 56563 56626 56635 56644 56653 56662 61666 62566 62656 62665 63466 63556 63565 63646 63655 63664 64366 64456 64465 64546 64555 64564 64636 64645 64654 64663 65266 65356 65365 65446 65455 65464 65536 65545 65554 65563 65626 65635 65644 65653 65662 66166 66256 66265 66346 66355 66364 66436 66445 66454 66463 66526 66535 66544 66553 66562 66616 66625 66634 66643 66652 66661
2016-03-22 22:27:18
上面程序有问题
参加下面
public ArrayList<String> nSumk(int n,int k){
String list = "";
ArrayList<String> result = new ArrayList<String>();
if(n<=0 || k< n || k > n*6 ) // 非法输入
return result;
DFS(n,1,k,result,list);
return result;
}
public void DFS(int n,int start,int k,
ArrayList<String> result,String list){
if(list.length() == n && k==0){
result.add(new String(list));
return;
}
for(int j=1;j<=6;j++){
if(k-j<0)
return;
k -=j;
list += j;
DFS(n,start+1,k,result,list );
k +=j;
list = list.substring(0,list.length() - 1);
// DFS(n,start+1,k-j,result,list + j);
}
}