LeetCode-39. Combination Sum

xiaoxiao2021-02-28  13

Given a set of candidate numbers (C(without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

All numbers (including target) will be positive integers.The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7, 

当遇到求某问题所有的解时,我们可以考虑采用回溯法进行求解。回溯法是将问题的解空间表示成树或者图的数据结构,再采用了深度优先搜索的思想,遍历得到问题的解,可以采用递归的方式实现。在搜索过程中可以使用剪枝函数来减少搜索的次数,提高运算的效率。

两篇入门文章的链接:

http://rapheal.iteye.com/blog/1526863

https://www.cnblogs.com/wuyuegb2312/p/3273337.html#frame

这里直接搬运来他们的算法框架

回溯法:

bool finished = FALSE; /* 是否获得全部解? */ backtrack(int a[], int k, data input)//k表示搜索深度,input表示其他的传递参数 { int c[MAXCANDIDATES]; /*这次搜索的候选 */ int ncandidates; /* 候选数目 */ int i; /* counter */ if (is_a_solution(a,k,input)) process_solution(a,k,input); else { k = k+1; construct_candidates(a,k,input,c,&ncandidates); for (i=0; i<ncandidates; i++) { a[k] = c[i]; make_move(a,k,input);//更新到原始数据结构上 backtrack(a,k,input); unmake_move(a,k,input);//撤销此次操作 if (finished) return; /* 如果符合终止条件就提前退出 */ } } } DFS:

/** * DFS核心伪代码 * 前置条件是visit数组全部设置成false * @param n 当前开始搜索的节点 * @param d 当前到达的深度 * @return 是否有解 */ bool DFS(Node n, int d){ if (isEnd(n, d)){//一旦搜索深度到达一个结束状态,就返回true return true; } for (Node nextNode in n){//遍历n相邻的节点nextNode if (!visit[nextNode]){// visit[nextNode] = true;//在下一步搜索中,nextNode不能再次出现 if (DFS(nextNode, d+1)){//如果搜索出有解 //做些其他事情,例如记录结果深度等 return true; } //重新设置成false,因为它有可能出现在下一次搜索的别的路径中 visit[nextNode] = false; } } return false;//本次搜索无解 } 回归到本题,此题可以直接套用上面的回溯法框架求解,传递的参数有:

a、用来保存最终结果的数组

b、存放搜索到的数字的临时数组

c、搜索的源数组

d、我们想要达到的目标,即离target还差多少数值

e、搜索的下标,即从源数组第几个数开始搜索

先将数组排序,方便剪枝。

class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> res=new ArrayList<>(); Arrays.sort(candidates); backTrack(res,new ArrayList<>(),candidates,target,0); return res; } private void backTrack(List<List<Integer>> res,List<Integer> tempList,int[] candidates,int remain,int start) { if(remain<0) return; else if(remain==0) res.add(new ArrayList<>(tempList)); else { for(int i=start;i<candidates.length;++i) { tempList.add(candidates[i]); backTrack(res,tempList,candidates,remain-candidates[i],i); tempList.remove(tempList.size()-1); } } } }

转载请注明原文地址: https://www.6miu.com/read-2250245.html

最新回复(0)