再帰関数を使ったプログラムのランタイムエラーを解決したい

Question

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.補足
アルゴリズム的な間違いというよりも、入力が多い場合に、処理に時間がかかりランタイムエラーが起こっているのかもしれません(実行時間の制約があります)。

もし再帰を使わない等のよりシンプルな解法がわかる方がいれば、解答して頂ければ幸いです。

Comments

[maisumakun]

> 入力によってはランタイムエラーが起きてしまう。

エラーメッセージなどはどのようなものでしょうか？

[ttp111]

ランタイムエラーです。とだけ言われます。
ソースコード→コンパイル→実行（ここで起きてるエラーがランタイムエラー)

申し訳ありませんが、具体的なエラーメッセージやランタイムエラーを起こす入力はわかりません。
入力によっては恐らく無限ループなどにハマってしまっているものと思われます。

[maisumakun]

実行環境はどのようなものですか？

[ttp111]

web上で実行できるプログラミングサイトです

[maisumakun]

別なサイトに乗り換えたほうがいいかもしれません。エラーを勝手に要約してしまうのは不親切です。

[actorbug]

入力する数値の最小・最大はいくつでしょうか。
入力する数値の個数の最小・最大はいくつでしょうか。

以下のような入力は許されるのでしょうか。

1
2147483648

[ttp111]

入力数値、個数の最大・最小は不明です。

そのような入力も許されます。

[jimbe]

何が入力されたのかも、ランタイムエラーというものが何なのかも分からないのでは、推測も難しいように思われます。
プログラミングサイトとは具体的に何処なのでしょうか。

[hoshi-takanori]

競プロならテストケースを考えることも問題に含まれます。

[actorbug]

ご提示のコードに、私が示した例を入力すると、以下のようなランタイムエラーになります。
Java における int の最大値(2147483647)を超えているためです。

Exception in thread "main" java.util.InputMismatchException: For input string: "2147483648"

また、もっと単純に、入力数値の個数に -1 を指定しても、以下のようなランタイムエラーになります。

Exception in thread "main" java.lang.NegativeArraySizeException: -1

このように、入力数値や個数に制限がないと、問題として成り立たなくなるため、何らかの制限が明示されているのが普通です。

[xebme]

↑つまり問題に、個数Nの範囲、数値の範囲などの制約が明示されているはず。
Nが大きい時、再帰がスタックオーバーフローするかが気になります。
(stackoverflowに質問するのもありです)
再帰をループに書き直すのはどうか。
ansをTreeSetにすれば重複排除、整列は不要。

[xebme]

N個の数字の冪集合の作り方は、もっと効率の良い方法がありそうです。調べてみましょう。
「ランタイムエラー」は調べてください。例外発生なのか、タイムアウトなのかなど、テストケースごとに結果が表示されていると思います。
この問題は、冪集合を作らず、和の集合に各数字を足した集合を加えることでも解けます。

Answer 1

エラーになる状況

問題の制約は、入力値だけでなく、実行時の制約があり、実行条件はわかりかねます。結果のエラーレポートを読んで考えましょう。

改善コード

全ての数(正の値)を足した和がオーバーフローしないという仮定を設けます。メソッドは、入力値の配列を引数にとり、重複の排除にSetを利用します。戻り値のTreeSetを順にアクセスすれば、昇順に値が取り出せます。

static Set<Integer> uniqueSums(int[] nums) {
    
    // 答えを追加していく集合
    Set<Integer> ans = new TreeSet<>();
    ans.add(0);

    // 和の集合を作成
    Set<Integer> tmp = new HashSet<>();
    for (int n : nums) {
      tmp.clear();
      for (int e : ans) {
        tmp.add(e + n);
      }
      ans.addAll(tmp);
    }

    return ans;

  }

これでも実行時エラーが起きるならTreeSetをやめるなどの方策が必要です。例えば、和の最大値がある数以下に決まっているなら配列を用意するなど。

コードにバグがあれば私の責任です。

追記(仕様について)

仕様の理解が正しいかどうか自信がありません。チェックプログラムを追記します。計算量はO(2^N)です。

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class SumExpressions {

  public static void main(String[] args) {
    listAll(new int[] {1,2,3,5,7});
  }
  
  static void listAll(int[] nums) {
    
    // 答えを追加していく集合
    List<String> ans = new ArrayList<>();
    ans.add("0");

    // 和の式を作成
    List<String> tmp = new ArrayList<>();
    for (int n : nums) {
      tmp.clear();
      for (String e : ans) {
        String s = e + "+" + n;
        tmp.add(s);
      }
      ans.addAll(tmp);
    }

    // 式の個数を出力
    System.out.println("size : 2^" + nums.length + " : " + ans.size());
    // 和の組み合わせを出力
    ans.stream().collect(
            Collectors.groupingBy(
                e -> Stream.of(e.split("\\+"))
                           .map(Integer::valueOf)
                           .collect(Collectors.summingInt(x -> x))
            )
        ).entrySet().stream()
        .sorted(Comparator.comparing(Map.Entry::getKey))
        .map(e -> e.getKey() + " : " + e.getValue())
        .forEach(System.out::println);
  }
}

Comments

[xebme]

追記コードが分かりにくいので置き換えました。