部分和問題
部分和問題(プログラミングコンテストチャレンジブック p34の設定)
整数の中からいくつか選び、その和をちょうどkにすることができるならYes、できないならNoを出力。
制約
アルゴリズム
部分和問題(プログラミングコンテストチャレンジブック p34にあるように深さ優先探索(DFS:Depth-First Search)で解いてみる。
を加えるor加えないで左右に分岐する2分木を考えると、状態数は。
コード
//※a_1 →a[0] import java.util.*; public class subset_sum { static Scanner scanner; public static void main(String[] args) { scanner = new Scanner(System.in); new subset_sum(); } subset_sum(){ int n = scanner.nextInt(); int[] a = new int[n]; for(int i = 0; i < n; i++) a[i] = scanner.nextInt(); int k = scanner.nextInt(); System.out.println( solve(n,a,k) ); } String solve(int n, int[] a, int k){ return DFS(0,0,n,a,k) ? "Yes" : "No"; } //i(aの添え字、加える or 加えないを決定した個数(深さに相当)), sum(ルートからカレントまで来たときの合計) boolean DFS(int i,int sum, int n, int[] a, int k){ if( i == n ) return sum == k; //n個決め終わったので、sum = k になっているかどうかを判定 if( DFS(i+1, sum+a[i], n, a, k) ) return true; //a[i]を使う if( DFS(i+1, sum, n, a, k) ) return true; //a[i]を使わない return false; } }