Java實作 藍橋杯VIP 算法訓練 和為T

問題描述

從一個大小為n的整數集中選取一些元素，使得它們的和等于給定的值T。每個元素限選一次，不能一個都不選。

輸入格式

第一行一個正整數n，表示整數集内元素的個數。

第二行n個整數，用空格隔開。

第三行一個整數T，表示要達到的和。

輸出格式

輸出有若幹行，每行輸出一組解，即所選取的數字，按照輸入中的順序排列。

若有多組解，優先輸出不包含第n個整數的；若都包含或都不包含，優先輸出不包含第n-1個整數的，依次類推。

最後一行輸出總方案數。

樣例輸入

5

-7 -3 -2 5 9

樣例輸出

-3 -2 5

-7 -2 9

2

資料規模和約定

1<=n<=22

T<=maxlongint

集合中任意元素的和都不超過long的範圍

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;


public class 和為T {
	  public static void main(String[] args) {
	        Scanner sc = new Scanner(System.in);
	        n = sc.nextInt();
	        isVisited = new boolean[n];
	        nums = new int[n];
	        for (int i = 0; i < n; i++) {
	            nums[i] = sc.nextInt();
	        }
	        t = sc.nextInt();
	        sc.close();
	        dfs(n - 1, 0, new LinkedList(), true);
	        while (!out.isEmpty()) {
	            System.out.println(out.pop());
	        }
	        System.out.println(cnt);
	    }
	    
	    private static int cnt = 0, n = 0, t = 0;
	    private static boolean[] isVisited;
	    private static int[] nums;
	    private static Stack out = new Stack<Integer>();
	    
	    private static void dfs(int pos, int tempT, LinkedList selectedNums, boolean isNone) {
	        for (int i = pos; i >= 0; i--) {
	            if (!isVisited[i]) {
	                isVisited[i] = true;
	                selectedNums.push(nums[i]);
	                dfs(i - 1, tempT + nums[i], selectedNums, false);
	                selectedNums.pop();
	                isVisited[i] = false;
	            }
	        }
	        if (tempT == t && !isNone) {
	            out.push(toReulstString(selectedNums.iterator()));
	            cnt++;
	        }
	    }
	    
	    private static String toReulstString(Iterator it) {
	        StringBuilder result = new StringBuilder();
	        while (it.hasNext()) {
	            result.append(it.next() + " ");
	        }
	        return result.toString();
	    }

}