0

非常に単純な質問:

配列を指定して、合計が値 k になるすべてのサブセットを見つけます

私はこれを Java でやろうとしていますが、O(n^2) 時間で解決する解決策を見つけたようです。このソリューションは正しい O(n^2) 実装ですか?

      @Test
    public void testFindAllSubsets() {
        int[] array = {4,6,1,6,2,1,7};
        int k=7;
                 // here the algorithm starts
        for(int i = 0; i < array.length;i++){
            // now work backwords
            int sum = array[i];
            List<Integer> subset = new ArrayList<Integer>();
            subset.add(array[i]);
            for(int j = array.length -1; j > i && sum < k; j--){
                int newSum = sum + array[j];
                                    // if the sum is greater, than ditch this subset
                if(newSum <= k){
                    subset.add(array[j]);
                    sum = newSum;
                }
            }
            // we won't always find a subset, but if we do print it out
            if(sum == k){
                System.out.print("{");
                System.out.print(subset.get(0));
                for(int l = 1; l < subset.size(); l++){
                    System.out.print(","+subset.get(l));
                }
                System.out.print("}");
                System.out.println();
            }
        }
    }

さまざまな例で試してみましたが、壊れているように見えるものは見つかりませんでした。ただし、オンラインで検索したところ、これは問題の一般的な解決策ではないようであり、多くの解決策はこの問題が O(2^n) であると主張しています。

PS これは宿題の質問ではありません。私は、Java で Comp Sci の基礎に取り組もうとしているブログラマーです。ありがとう！

4

2 に答える 2

2

いいえ、これは正しくありません。この簡単な例を見てください

配列は 4,6,1,2,3,1 で、ターゲットの合計は 7 で、ロジックでは (4,3) (6,1) (1,2,3,1) しか見つかりません。 (4,2,1)、(4,3)。

私はウィキを参照することを参照します

于 2013-08-10T04:17:35.267 に答える
1

洗練された解決策は、「私は参加しているかどうか」という質問に答える各メンバーとしてサブセットを単純に考えることです。したがって、基本的にそれぞれが「はい/いいえ」と答えることができるため、2 N 個のサブセット (空のサブセットを含む) があります。これをコード化する最も自然な方法は、各要素を再帰的に処理し、次のいずれかを実行することです。

  1. それを選ぶ
  2. スキップする

したがって、最悪の場合に非常に多くの答えが考えられるため、時間の複雑さは O(2 N ) になります。

于 2013-08-10T07:49:00.843 に答える