回溯算法

//vector 动态数组  
//int arr[10] 数组 
vector<int> arr;
//增 
arr.push_back(1); 
//删
arr.pop_back();
//改
arr[1] = 3;
//查 
arr[2];
//元素个数
arr.size() 

递归：

#1.返回值+参数 
#2.结束条件
#3.递归式 

#回溯算法： 1.本质就是递归 2.搜索：穷举算法（） 3.场景： 1.组合 n=1234 k=2 12 13 14.... 2.切割问题： s="XXXXX" 特定条件 3.排列 4.棋盘：N皇后

模版：
void backtracking(参数){
	if(结束条件){
		存储数据
		return ; 
	} 
	for(遍历剩余节点){
		处理节点
		backtracking(参数)
		回溯撤销结果 
	}
}		

void backtracking(int n,int k,int start){
	if(temp.size() ==k){
		ans.push_back(temp);
		return ; 
	} 
	for(int i = start ;i<=n;i++){
		temp.push_back(i);
		backtracking(n,k,i+1);
		temp.pop_back(); 
	}
}

freopen("A.in",stdin);
freopen("A.out",stdout);

第二题

void backtracking(int tarsum,int k,int start,sum){
	if(temp.size() ==k){
		if(sum==tarsum)ans.push_back(temp);
		return ; 
	} 
	for(int i = start ;i<=9;i++){
		sum+=i;
		temp.push_back(i);
		backtracking(n,k,i+1,sum);
		sum-=i;
		temp.pop_back(); 
	}
}