备案个人可以做视频网站,网络营销广告词有哪些,百度指数入口,连城县住房和城乡建设局 网站题目描述 找出所有相加之和为 n 的 k 个数的组合#xff0c;且满足下列条件#xff1a;只使用数字1到9。每个数字 最多使用一次。返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次#xff0c;组合可以以任何顺序返回。
解析 递归加剪枝#xff0c;搜索长度达…题目描述 找出所有相加之和为 n 的 k 个数的组合且满足下列条件只使用数字1到9。每个数字 最多使用一次。返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。
解析 递归加剪枝搜索长度达到k就可以返回另外当选择的数之和比n还大的时候就可以不用再搜索了。
public ListListInteger combinationSum3(int k, int n) {ListListInteger res new ArrayList();boolean[] isChosen new boolean[10];ListInteger current new ArrayList();DFS(res, current, isChosen, 0, k, n, 1);return res;}private void DFS(ListListInteger res,ListInteger current,boolean[] isChosen,int curSum,int k,int n,int start) {if(current.size() k) {if(curSum n) {res.add(new ArrayList(current));}return;}for(int i start; i 9 ; i) {if(!isChosen[i]) {current.add(i);curSum i;if(curSum n) {isChosen[i] true;DFS(res, current, isChosen, curSum, k, n, i 1);}current.remove(current.size() - 1);curSum - i;isChosen[i] false; // 回溯}}}
