题目1（整数拆分）
将一个正整数N分解成几个正整数相加，可以有多种分解方法，
例如7=6+1，7=5+2，7=5+1+1，...编程求出正整数N的所有整数分解式子。
输入格式：
每个输入包含一个测试用例，即正整数N (0<N≤30)。
输出格式：
按递增顺序输出N的所有整数分解式子。
递增顺序是指：对于两个分解序列N1={n1,n2,⋯}和N2={m1,m2,⋯}，
若存在i使得n1=m1,⋯,ni=mi，但是n(i+1)<m(i+1),则N1序列必定在N2序列之前输出。
每个式子由小到大相加，式子间用分号隔开，且每输出4个式子后换行。
输入样例：
7
输出样例：
7=1+1+1+1+1+1+1;7=1+1+1+1+1+2;7=1+1+1+1+3;7=1+1+1+2+2
7=1+1+1+4;7=1+1+2+3;7=1+1+5;7=1+2+2+2
7=1+2+4;7=1+3+3;7=1+6;7=2+2+3
7=2+5;7=3+4;7=7
代码1：（n如果过百就可能超时）
#include "stdio.h"
int n,sum,ans;
int a[100];
void dfs(int step,int x)
{//step代表站在第几个盒子面前，x代表当前的放的最小数
int i;
if(sum==n)//如果此刻相等，那么此刻盒子里未放东西
{
printf("%d=",n);
for(i=1;i<=step-1;i++)
if(i==1)
printf("%d",a[i]);
else
printf("+%d",a[i]);
ans++;
if(ans%4==0)
printf("\n");
else
{
if(step!=2)
printf(";");
}
return;
}
else if(sum>n)
return;
for(i=x;i<=n;i++)//每次放的数都必须>=上一次的数
{
a[step]=i;
sum+=a[step];
dfs(step+1,i);
sum-=a[step];//此刻盒子里的数要取出来放别的数
}
return;
}
int main()
{
while(~scanf("%d",&n)){
sum=0;ans=0;
dfs(1,1);//站在第一个盒子面前，准备放1
}
return 0;
}
题目2：（相对题目1增添了条件）
将整数n分成k份，且每份不能为空，问有多少种不同的分法。
当n=7,k=3时，下面三种分法被认为是相同的：
（1，1，5），（1，5，1），（5，1，1）
输入描述:
一行两个数n,m。（6<=n<=200，2<=m<=6）
输出描述:
一行一个整数，即不同的分法数。
代码2：（注意其中的改动，比上一个代码省大量的时间）
当然如果用动态规划来写，更节约时间
/*
将整数n分成k份，相当于我手上有着许多张（1-n）的牌
我需要取任意三张牌分别放到三个盒子里面，且需要避免重复
*/
#include<stdio.h>
int a[10];//用来放置拆分后的数字
int n,m,ans,sum;
void dfs(int step,int x)
{//step表示此刻站在第几个的盒子面前
if(sum>n)//如果已经超过的n，接下来的盒子肯定没有办法放牌了
return;
//我们走到m个盒子面前，因为这是最后一个要放的盒子，
所以我们没有必要非要再往里面放牌了，
我们判定将要放的牌是否可以放到盒子里面即可，
这样可以少往后搜一次，自然可以大量节约时间
if(step==m)
{
if(n-sum>=x)//判定第m个盒子可以放>=x的牌不，这是一种放法
ans++;
return;
}
int i;
for(i=x;i<=(n-sum)/(m-step+1);i++)//牌按着从小到大排序，这样可有效的避免重复
{ //i的取值[x,(n-sum)/(m-step+1)];
a[step]=i; //前step-1个盒子已放好，剩下的盒子数为(m-step+1)
sum+=i; //此刻sum表示已放好的值，n剩下的为(n-sum)
dfs(step+1,i);
sum-=i;
}
return ;
}
int main()
{
ans=0;sum=0;
scanf("%d %d",&n,&m);
dfs(1,1);//站在第一个盒子面前我准备放1
printf("%d\n",ans);
return 0;
}
题目3：（相对题目2又增添了条件）
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，
问共有多少种不同的分法？（用K表示）
5，1，1和1，5，1 是同一种分法。
Input
第一行是测试数据的数目t（0 <= t <= 20）。
以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
Output
对输入的每组数据M和N，用一行输出相应的K。
Sample Input
1
7 3
Sample Output
8
代码3（n也不能太大）：（可以用的动态规划来写，省时）
苹果数是一个整数，拆分放到盘子里面
相当于整数拆分，只是这里可以有空盘子
#include<stdio.h>
int a[10];//用来放置拆分后的数字
int n,m,ans,sum;
void dfs(int step,int x)
{
if(sum>n)
return;
if(sum==n)//只要盘子不用多，少用盘子我们也可以算一中放法
{
ans++;
return;
}
if(step==m+1)//没有（m+1）个盘子，因此不可能放苹果
return;
int i; //这里必须是n，因为没有办法判定会放到多少个盘子里
for(i=x;i<=n;i++)//牌按着从小到大排序，这样可有效的避免重复
{
a[step]=i;
sum+=i;
dfs(step+1,i);
sum-=i;
}
return ;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
ans=0;sum=0;
scanf("%d %d",&n,&m);
dfs(1,1);//站在第一个盘子面前放1，不是说有的盘子可以不放吗，请看上面 dfs（if(step>m+1)）
printf("%d\n",ans);
}
return 0;
}
题目4：（放牌，相比全排列难了一些）
题目描述
小明被劫持到X赌城，被迫与其他3人玩牌。
一副扑克牌（去掉大小王牌，共52张），均匀发给4个人，每个人13张。
这时，小明脑子里突然冒出一个问题：
如果不考虑花色，只考虑点数，也不考虑自己得到的牌的先后顺序
自己手里能拿到的初始牌型组合一共有多少种呢？
输出
请输出该整数，不要输出任何多余的内容或说明文字。
代码4：
/*
分析：
方法1：深搜
题上说了，不考虑花色，那么题意就变为：13种牌，每种牌各有4张一样的
题上又说，不考虑取牌的顺序，那么我们就没有必要一张一张的取牌了，
我们可以一次拿多 张，也不可以不拿，可以多拿几次，也可以少拿几次
这里为了我们取牌方便，我们把同一种类的放在一块，那么就变成了13堆，
当我们站在不同的堆面前，我们可以拿0或1或2或3或4张，然后继续去下一堆拿牌
当我们恰好拿够13张时，我们就可以ans+1了，之后返回，
然后再把我们最后一次拿的牌放回去，看看是否可以继续选择别的种类的牌，
这样的话，其实就是深搜返回的过程了
方法2：暴力
还可以13层for循环（i=0;i<=4;i++）
满足条件i+j+k+l+m+l+n+o+p+q+r+s+t==13
*/
#include<stdio.h>
int ans;
void dfs(int step,int sum)
{//step表示第几堆，sum表示手中的牌数
if(step==14)//不存在第14堆
return ;
int i;
for(i=0;i<=4;i++)
{
sum+=i;//一次性在x堆拿i张牌
//如果在该堆取i张恰好达到13张，就可以直接返回了，
因为如果再去取i++，牌数一定会大于13的，牌数永远不会超过13张，
这样也节省了时间
if(sum==13)
{
ans++;
return;
}
dfs(step+1,sum);//去下一堆
sum-=i;//把i张牌再放回去,选择再去拿i+1张牌
}
return;
}
int main()
{
ans=0;
dfs(1,0);//站在第一堆面前，起初手中为0张牌
printf("%d\n",ans);
return 0;
}
本文地址：https://blog.csdn.net/Helinshan/article/details/109258127