招银测开社招笔试题
求n个正整数构成的⼀个给定集合A = {a1,a2,a3,…,an}的⼦集，⼦集的和要等于24。请输出所有符合条件的⼦集。思路：状态树
转载⾃
import java.util.Scanner;
public class Main {
public static int cnt=0;
public static int getSum(int[] arr,boolean[] visit){
int sum=0;
for(int i=0;i<arr.length;i++){
if(visit[i]){
sum+=arr[i];
}
}
return sum;
}
public static void backTrack(int cur,int[] arr,boolean[] visit){
if(cur==arr.length){
if(getSum(arr,visit)==24){
cnt++;
System.out.println("path:");
for(int i=0;i<arr.length;i++){
if(visit[i]){
System.out.print(arr[i]+" ");
}
}
System.out.println();
}
return;
}
else{
visit[cur]=true;
backTrack(cur+1,arr,visit);
visit[cur]=false;
backTrack(cur+1,arr,visit);
}
}
public static void main(String[] args){
Scanner in =new Scanner(System.in);
while(in.hasNextLine()){
System.out.println("input n :");
int n = in.nextInt();
读取了⼀个字符但并没有读取换⾏符，因此需要单独读取⼀次回车
System.out.println("input str :");
String Line();
String[] tmp=str.split("\\s+");
int[] arr=new int[n];
boolean[] visit=new boolean[n];
for(int i=0;i<n;i++){
arr[i]=Integer.valueOf(tmp[i]).intValue();
visit[i]=false;
}
cnt=0;
backTrack(0,arr,visit);
System.out.println(cnt);
}
}
}
输⼊：
5
1 3 5 16 2
笔试题7
22 4 5 2 16 3 4