1.実現したいこと
以下のように、入力された数値の和の組み合わせを全て昇順で出力するプログラムを組みたい。
入力例:
2⇦入力される個数
1
3
出力例:
4⇦出力される個数
0(何も足していない)
1(1のみ)
3(3のみ)
4(1+3)
2.発生している問題
入力によってはランタイムエラーが起きてしまう。
3.該当のソースコード
import java.util.*; public class Main { //答えを追加していくリスト static List<Integer> ans = new ArrayList<>(); //入力を受け取る配列 static int[] nums; //再起関数を使って全パターンを考える //patternという配列をnumsと比べ、patteran[i]が0のときにnums[i]をscoreに足し、 //足し終わったscoreをansに追加していく static void combination(int pattern[], int n, int num_decided){ if(num_decided==n){ int score = 0; for(int i=0; i<n; i++){ if(pattern[i] == 0){ score += nums[i]; } } ans.add(score); return; } //pattern[i]が0ならnums[i]をscoreに足す pattern[num_decided] = 0; combination(pattern,n,num_decided + 1); //pattern[i]が1ならnums[i]をscoreに足さない pattern[num_decided] = 1; combination(pattern,n,num_decided + 1); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); //入力の個数を受け取る int n = sc.nextInt(); nums = new int[n]; int[] pattern = new int[n]; int num_decided = 0; //入力を受け取る for(int i=0; i<n; i++){ nums[i] = sc.nextInt(); } combination(pattern,n,num_decided); //重複した数値を消去 List<Integer> ansDrop = new ArrayList<>(new HashSet<>(ans)); //昇順に並べる Collections.sort(ansDrop); //出力個数を出力 System.out.println(ansDrop.size()); //和の組み合わせを出力 for(int i=0; i<ansDrop.size(); i++){ System.out.println(ansDrop.get(i)); } } }
4.ソースコードの追加解説
再帰関数combinationの部分では入力例の場合、
pattern={0,0}
pattern={0,1}
pattern={1,0}
pattern={1,1}
とnums={1,3}を見比べ、pattern[i]が0の時はscoreにnums[i]を足し、1の時は足さないという作業をすることで、
score=0
score=3
score=1
score=4
をそれぞれ作り出し、ansというリストに追加している、ことを意図しています。
5.何を教えて欲しいのか
どのような入力の場合にランタイムエラーが起きてしまうのか、またそれはなぜ起きてしまうのかも出来れば教えていただきたいです。
6.補足
アルゴリズム的な間違いというよりも、入力が多い場合に、処理に時間がかかりランタイムエラーが起こっているのかもしれません(実行時間の制約があります)。
もし再帰を使わない等のよりシンプルな解法がわかる方がいれば、解答して頂ければ幸いです。