招银 测开 社招笔试题

求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();
            in.nextLine();//这里的作用的因为nextInt是读取了一个字符但并没有读取换行符，因此需要单独读取一次回车
            System.out.println("input str :");
            String str=in.nextLine();
            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