题目大意
给定整数序列a1,a2,...,an,判断是否可以从中选出若干数,使它们的和恰好为k.
1≤n≤20
-10^8≤ai≤10^8
-10^8≤k≤10^8
输入
n=4
a={1,2,4,7}
k=13
输出:
Yes (13 = 2 + 4 + 7)
分析
使用两种方法解决该问题
第一种
getSubsets
是巧用二进制 按字典序顺序求出子集
第二种
dfs深度优先搜索,当我们面对选择的时候 只有
要
和不要
这个数字去sum,注意点就是 ArrayList在要完之后 记得回溯

dfs的出口
- 符合 k被刚好减完
- 不符合
- k是负数 或者 cur超出数组length
代码
package BlueCup.Seven_recursion;
import java.util.ArrayList;
import java.util.Arrays;
public class Dfs2部分和 {
static int kk;
public static void main(String[] args) {
int[] a = new int[]{1, 2, 4, 7};
int n = a.length;
int k = 13;
kk = k;
getSubsets(a, n, k);
dfs(a, k, 0, new ArrayList<>());
}
private static void dfs(int[] a, int k, int cur, ArrayList<Integer> ints) {
if (k == 0) {
System.out.print("Yes ("+kk+" = ");
for (int i = 0; i < ints.size(); i++) {
System.out.print(ints.get(i)+(ints.size()-1!=i?" + ":")"));
}
System.exit(0);
}
if (k < 0 | cur == a.length) {
return;
}
dfs(a, k, cur + 1, ints);//不要
ints.add(a[cur]);
int index = ints.size() - 1;
dfs(a, k - a[cur], cur + 1, ints);//要
ints.remove(index);
}
/**
* 二进制迭代法求子集
*
* @param A
* @param n
* @param k
* @return
*/
public static ArrayList<ArrayList<Integer>> getSubsets(int[] A, int n, int k) {
Arrays.sort(A);//正序排序
ArrayList<ArrayList<Integer>> res = new ArrayList<>();//大集合
for (int i = (int) Math.pow(2, n) - 1; i > 0; i--) {//大数字减1
ArrayList<Integer> s = new ArrayList<>();//对每个i建立集合
int sum = 0;
for (int j = n - 1; j >= 0; j--) {
//检查哪个位上的二进制为1,从高位开始检查,高位对应这素组靠后的元素
if (((i >> j) & 1) == 1) {
s.add(A[j]);
sum += A[j];
}
}
if (sum == k) {
for (int j = 0; j < s.size(); j++) {
System.out.print(s.get(j) + (j != s.size() - 1 ? "+" : ""));
}
System.out.println();
}
res.add(s);
}
return res;
}
}
本文作者:Author: 寒光博客
文章标题:[挑战程序设计] 部分和—— dfs和巧用二进制迭代求子集
本文地址:https://dxoca.cn/Algorithm/218.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/Algorithm/218.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。