再帰関数 バックトラッキング 部分集合 java

Question

前提・実現したいこと

三つの変数を用いて、要素の和が指定した値と同じになる部分集合を書き出すという問題になっているのですが、バックトラッキングを使って導けるのではないかというところまでは分かったのですが、集合の中身の要素の変動を全て把握し、書き出すことが難しくなかなか解けませんでした。
解答がないので、理解するために何かしら考え方のヒントだけでも貰いたいです。

出力例：3の場合、{3},{1,2},{1,1,1}
４の場合、{4},{1,3},{2,2},{1,1,2},{1,1,1,1}

発生している問題・エラーメッセージ

エラーメッセージ

該当のソースコード

public static void main(String []args){
        bfDfs_demand(n,i,k);
     }
void btDfs_demand(int n, int i, int k) {
  if () {
    
    return ;
  }
  

  }
int getChoice(int n,int i, int k){

}
int write(int n,int i,int k){//この関数で出力
}

//これが考えた構造です。
### 試したこと

サイズが大きい順から考えていく。
例：4の時、
{1,1,1,1}　　→　要素の１同士を足して、　{1,1,2}   →　要素の１同士、また１と２を足して　{1,3},{2,2}　　→　　{4}
問題　集合が重複してしまう。

 1を起点として考える。
println(",1")というようにあらかじめ1が入るような設定をしておく。
問題　6の時とかに{2,2,2}が入らない。

### 補足情報（FW/ツールのバージョンなど）

できれば、バックトラッキングを使って解きたいです。

Comments

[mather]

ソースコードの記載がおかしくなっています。プレビューで確認し、ソースコードの記載の末尾に ``` を追加してソースコードの終了部分を明確にしないとマークダウンが正しく機能しません。

また、ソースコードがどう見ても空っぽで、考え方を記載したのみで何も実装されていないように見受けられます。
「試したこと」に記載した内容をまず実装してから質問に記載してください。
「バックトラッキング」という言葉についても、どういう意味で習ったのか自分の言葉で説明してみましょう。調べ直すことでヒントになるかもしれません。

最後に、もし学校の問題なら学校で質問してくださいね。

[arch]

返答ありがとうございます。
もう一回自分で見直してみます。

Answer 1

要素の和を n とすると、全部 1 が一番長い部分集合になるので、
大きさ n の配列を用意して、大きい数から詰め込んで行くことにします。
まだ和に達していなければ、左側以下の値を大きいものから順に 1 になるまで
詰め込んで、次に行くというのを繰り返せばよいでしょう。

ヒントとして書くのが難しいので、コードで書きます。

import java.util.Scanner;

class Main {
	public static void main(String []args){
		Scanner sc = new Scanner(System.in);
		for (;;) {
			System.out.print(">> ");
			if (!sc.hasNextInt()) break;
			int n = sc.nextInt();
			new Sum(n).gen(0, n, n);
		}
	}
}

class Sum {
	int a[];

	Sum(int n) {
		a = new int[n];
	}

	void gen(int i, int k, int r) {
		if (r == 0) {  // 和ができたので表示
			for (int j = 0; j < i; j++)
				System.out.print(" " + a[j]);
			System.out.println();
		}
		else if (r > 0)  // まだ和に達していない
			for (int j = k; j > 0; j--) {
				a[i] = j;
				gen(i+1, j, r - j);  // 再帰呼出し
			}
	}
}

追記
gen を static にして、Sumクラスを使わずに、
さらに、和を引数で与えるようにしてみました。

import java.util.Arrays;

class Main {
    public static void main(String []args){
        for (int i = 0; i < args.length; i++) {
            int n = Integer.parseInt(args[i]);
            if (i > 0) System.out.println();
            gen(new int[n], 0, n, n);
        }
    }

    static void gen(int[] a, int i, int j, int r) {
        if (r == 0)  // 和ができたので表示
            System.out.println(Arrays.toString(Arrays.copyOf(a, i)));
        else if (r > 0)  // まだ和に達していない
            for (; j > 0; j--) {
                a[i] = j;
                gen(a, i + 1, j, r - j);  // 再帰呼出し
            }
    }
}

実行例

$ java Main 3 4
[3]
[2, 1]
[1, 1, 1]

[4]
[3, 1]
[2, 2]
[2, 1, 1]
[1, 1, 1, 1]

追記2
Math.min を使うと、else if (r > 0) が else で済みますね。

    static void gen(int[] a, int i, int j, int r) {
        if (r == 0)  // 和ができたので表示
            System.out.println(Arrays.toString(Arrays.copyOf(a, i)));
        else  // まだ和に達していない
            for (j = Math.min(j, r); j > 0; j--) {
				a[i] = j;
				gen(a, i + 1, j, r - j);  // 再帰呼出し
            }
    }

gen の呼び出し回数も減ります。

追記3
xebme さんのコードに刺激されて、for文を再帰呼出しに変えてみました。

import java.util.Arrays;

class Main {
	public static void main(String []args){
		int n = 6;
		gen(new int[n], 0, n, n);
	}

	static void gen(int[] a, int i, int j, int r) {
		if (r == 0)  // 和ができたので表示
			System.out.println(Arrays.toString(Arrays.copyOf(a, i)));
		else  {  // まだ和に達していない
			a[i] = j = Math.min(j, r);
			gen(a, i + 1, j, r - j);
			if (--j > 0) gen(a, i, j, r);
		}
	}
}

和の n は、ハードコーディングしました。
Scanner による標準入力や、args によるコマンドライン引数に
変えるのは簡単でしょう。

Answer 2

仕様の不明点

引数(int n,int i, int k)の意味がわかりません。できれば追記をお願いします。

課題検討

与えられた数(n)が和になる、整数(1<=i<=n)の全ての組み合わせを求める課題だと思います。再帰で利用するため文字列をアキュムレータとして使っています。簡単すぎてかえって自信がありません。誤りがあれば指摘してください。繰り返し解くならメモ化してもよいかもしれません。

public class q353621 {

  public static void main(String[] args) {
    for (int i = 1; i < 10; ++i) {
      checkRemainder(i, i, /* i, */ "");
      System.out.println();
    }
  }

  static void checkRemainder(int rem, int divisor, /* int v,*/ String accum) {
    
    if (divisor == 0) return;
    if (rem == divisor) {
       // 余りがない -> 完了
      System.out.println(accum + ((accum.length()==0)?"":",") + divisor);
    } else if (rem > divisor){
      // 余りがある
      checkRemainder(rem - divisor, divisor, /* v,*/ accum + ((accum.length()==0)?"":",") + divisor);
    }
    /* if (rem == v) accum = ""; */
    checkRemainder(rem, divisor - 1, /* v,*/ accum);

  }

}

結果も添付します。

1

2
1,1

3
2,1
1,1,1

4
3,1
2,2
2,1,1
1,1,1,1

5
4,1
3,2
3,1,1
2,2,1
2,1,1,1
1,1,1,1,1

6
5,1
4,2
4,1,1
3,3
3,2,1
3,1,1,1
2,2,2
2,2,1,1
2,1,1,1,1
1,1,1,1,1,1

7
6,1
5,2
5,1,1
4,3
4,2,1
4,1,1,1
3,3,1
3,2,2
3,2,1,1
3,1,1,1,1
2,2,2,1
2,2,1,1,1
2,1,1,1,1,1
1,1,1,1,1,1,1

8
7,1
6,2
6,1,1
5,3
5,2,1
5,1,1,1
4,4
4,3,1
4,2,2
4,2,1,1
4,1,1,1,1
3,3,2
3,3,1,1
3,2,2,1
3,2,1,1,1
3,1,1,1,1,1
2,2,2,2
2,2,2,1,1
2,2,1,1,1,1
2,1,1,1,1,1,1
1,1,1,1,1,1,1,1

9
8,1
7,2
7,1,1
6,3
6,2,1
6,1,1,1
5,4
5,3,1
5,2,2
5,2,1,1
5,1,1,1,1
4,4,1
4,3,2
4,3,1,1
4,2,2,1
4,2,1,1,1
4,1,1,1,1,1
3,3,3
3,3,2,1
3,3,1,1,1
3,2,2,2
3,2,2,1,1
3,2,1,1,1,1
3,1,1,1,1,1,1
2,2,2,2,1
2,2,2,1,1,1
2,2,1,1,1,1,1
2,1,1,1,1,1,1,1
1,1,1,1,1,1,1,1,1

Comments

[kazuma-s]

if (rem == v) accum = "";
この行は要らないでしょう。
rem == v ということは再帰呼出しのトップレベルであり、
accum は元から "" です。

[kazuma-s]

ということは、checkRemainder の引数 v は要らなくなるでしょう。

[xebme]

kazuma-sさん、ありがとうございます。

引数vを削除しました。当初は２引数で作成していました。バグがあったため、vを追加しましたが、勘違いでした。

質問が３引数なのは、アキュムレータ用の配列のインデックスかもしれないと思います。

Answer 3

要件を満たしていないので答えにはなりませんが、ヒントになるか(ならないか)ということで、動作するモノを出してみます。
ハノイの塔のように '1' をあちこちに移動させている感じです。

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Q353621 {
  public static void main(String[] args) {
    int n = 6; //要素の和

    int buf[] = new int[n];
    buf[0] = n+1;
    Set<String> done = new HashSet<>();
    int i = 0;
    do {
      //パターン生成
      if(i > 0) buf[i-1] ++;
      for(int j=--buf[i--]; j > 0; j--) buf[++i] = 1;
      //既存チェック・表示
      String s = Arrays.toString(Arrays.stream(buf, 0, i+1).sorted().toArray());
      if(done.add(s)) System.out.println(s);
    } while(i > 0);
  }
}

[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 2]
[1, 1, 1, 3]
[1, 1, 2, 2]
[1, 1, 4]
[1, 2, 3]
[1, 5]
[2, 2, 2]
[2, 4]
[3, 3]
[6]