他の誰も試みていないので、少なくとも部分的な解決策を投入したほうがよいでしょう。以前のコメントで指摘したように、この問題はサブセット和問題の変形であり、この解決策を開発する際に、この問題に対する文書化されたアプローチに大きく依存してきました。
subsetsWithSum(A, k, s)合計が s になる A の k-length サブセットをすべて計算する関数を作成しようとしています。この問題は、次の 2 つの方法で再帰的な解決に役立ちます。
- subsetsWithSum(x 1 ... x n , k, s) の解は、subsetsWithSum(x 2 ... x n , k, s) を計算し、x 1 を含むすべての有効なサブセット (存在する場合) を追加することによって見つけることができます。; と
- 要素 x iを含むすべての有効なサブセットは、subsetsWithSum(A - x i , k-1, sx i ) を計算し、結果の各サブセット (存在する場合) にx iを追加することによって見つけることができます。
k が 1 の場合、再帰の基本ケースが発生します。この場合、subsetsWithSum(A, 1, s) の解は、その要素が s に等しいすべての単一要素サブセットのセットです。
したがって、ソリューションへの最初の刺し傷は次のようになります
/**
* Return all k-length subsets of A starting at offset o that sum to s.
* @param A - an unordered list of integers.
* @param k - the length of the subsets to find.
* @param s - the sum of the subsets to find.
* @param o - the offset in A at which to search.
* @return A list of k-length subsets of A that sum to s.
*/
public static List<List<Integer>> subsetsWithSum(
List<Integer> A,
int k,
int s,
int o)
{
List<List<Integer>> results = new LinkedList<List<Integer>>();
if (k == 1)
{
if (A.get(o) == s)
results.add(Arrays.asList(o));
}
else
{
for (List<Integer> sub : subsetsWithSum(A, k-1, s-A.get(o), o+1))
{
List<Integer> newSub = new LinkedList<Integer>(sub);
newSub.add(0, o);
results.add(0, newSub);
}
}
if (o < A.size() - k)
results.addAll(subsetsWithSum(A, k, s, o+1));
return results;
}
ここで、このソリューションは、以前に呼び出されたのと同じ一連の引数を使用して、subsetsWithSum(...) を呼び出すことが多いことに注意してください。したがって、subsetsWithSum はメモ化されることを懇願するだけです。
関数をメモするために、引数 k、s、o を 3 つの要素リストに入れました。これは、これらの引数から以前に計算された結果 (存在する場合) へのマップのキーとなります。
public static List<List<Integer>> subsetsWithSum(
List<Integer> A,
List<Integer> args,
Map<List<Integer>, List<List<Integer>>> cache)
{
if (cache.containsKey(args))
return cache.get(args);
int k = args.get(0), s = args.get(1), o = args.get(2);
List<List<Integer>> results = new LinkedList<List<Integer>>();
if (k == 1)
{
if (A.get(o) == s)
results.add(Arrays.asList(o));
}
else
{
List<Integer> newArgs = Arrays.asList(k-1, s-A.get(o), o+1);
for (List<Integer> sub : subsetsWithSum(A, newArgs, cache))
{
List<Integer> newSub = new LinkedList<Integer>(sub);
newSub.add(0, o);
results.add(0, newSub);
}
}
if (o < A.size() - k)
results.addAll(subsetsWithSum(A, Arrays.asList(k, s, o+1), cache));
cache.put(args, results);
return results;
}
subsetsWithSum 関数を使用して、合計が 0 になるすべての k-length サブセットを計算するには、次の関数を使用できます。
public static List<List<Integer>> subsetsWithZeroSum(List<Integer> A, int k)
{
Map<List<Integer>, List<List<Integer>>> cache =
new HashMap<List<Integer>, List<List<Integer>>> ();
return subsetsWithSum(A, Arrays.asList(k, 0, 0), cache);
}
残念ながら、私の複雑さの計算スキルは少し (非常に) さびているので、他の誰かがこのソリューションの時間の複雑さを計算するのを手伝ってくれることを願っていますが、それは力ずくのアプローチの改善になるはずです。
編集：わかりやすくするために、上記の最初のソリューションは、時間の複雑さにおいてブルートフォースアプローチと同等である必要があることに注意してください。関数のメモ化は多くの場合に役立ちますが、最悪の場合、キャッシュには有用な結果が含まれず、時間の複雑さは最初のソリューションと同じになります。また、部分和問題はNP 完全であることにも注意してください。これは、どの解も指数関数的な時間の複雑さを持つことを意味します。編集を終了します。
完全を期すために、これを次のようにテストしました。
public static void main(String[] args) {
List<Integer> data = Arrays.asList(9, 1, -3, -7, 5, -11);
for (List<Integer> sub : subsetsWithZeroSum(data, 4))
{
for (int i : sub)
{
System.out.print(data.get(i));
System.out.print(" ");
}
System.out.println();
}
}
そしてそれは印刷されました：
9 -3 5 -11
9 1 -3 -7