teratail
回答率
85.35%
teratail header banner
teratail header banner
質問するログイン新規登録
トップJavaに関する質問再帰関数　バックトラッキング　部分集合　java

編集履歴

回答編集履歴

7

追記3

2021/08/11 11:30

投稿

kazuma-s
kazuma-s

スコア8224

test CHANGED
@@ -189,3 +189,57 @@
189
189
 
190
190
 
191
191
  gen の呼び出し回数も減ります。
192
+
193
+
194
+
195
+ **追記3**
196
+
197
+ xebme さんのコードに刺激されて、for文を再帰呼出しに変えてみました。
198
+
199
+ ```Java
200
+
201
+ import java.util.Arrays;
202
+
203
+
204
+
205
+ class Main {
206
+
207
+ public static void main(String []args){
208
+
209
+ int n = 6;
210
+
211
+ gen(new int[n], 0, n, n);
212
+
213
+ }
214
+
215
+
216
+
217
+ static void gen(int[] a, int i, int j, int r) {
218
+
219
+ if (r == 0) // 和ができたので表示
220
+
221
+ System.out.println(Arrays.toString(Arrays.copyOf(a, i)));
222
+
223
+ else { // まだ和に達していない
224
+
225
+ a[i] = j = Math.min(j, r);
226
+
227
+ gen(a, i + 1, j, r - j);
228
+
229
+ if (--j > 0) gen(a, i, j, r);
230
+
231
+ }
232
+
233
+ }
234
+
235
+ }
236
+
237
+ ```
238
+
239
+
240
+
241
+ 和の n は、ハードコーディングしました。
242
+
243
+ Scanner による標準入力や、args によるコマンドライン引数に
244
+
245
+ 変えるのは簡単でしょう。

6

追記2

2021/08/11 11:30

投稿

kazuma-s
kazuma-s

スコア8224

test CHANGED
@@ -159,3 +159,33 @@
159
159
  [1, 1, 1, 1]
160
160
 
161
161
  ```
162
+
163
+ **追記2**
164
+
165
+ `Math.min` を使うと、`else if (r > 0)` が `else` で済みますね。
166
+
167
+ ```Java
168
+
169
+ static void gen(int[] a, int i, int j, int r) {
170
+
171
+ if (r == 0) // 和ができたので表示
172
+
173
+ System.out.println(Arrays.toString(Arrays.copyOf(a, i)));
174
+
175
+ else // まだ和に達していない
176
+
177
+ for (j = Math.min(j, r); j > 0; j--) {
178
+
179
+ a[i] = j;
180
+
181
+ gen(a, i + 1, j, r - j); // 再帰呼出し
182
+
183
+ }
184
+
185
+ }
186
+
187
+ ```
188
+
189
+
190
+
191
+ gen の呼び出し回数も減ります。

5

copyOfRange を copyOf に変更

2021/08/11 05:39

投稿

kazuma-s
kazuma-s

スコア8224

test CHANGED
@@ -116,7 +116,7 @@
116
116
 
117
117
  if (r == 0) // 和ができたので表示
118
118
 
119
- System.out.println(Arrays.toString(Arrays.copyOfRange(a, 0, i)));
119
+ System.out.println(Arrays.toString(Arrays.copyOf(a, i)));
120
120
 
121
121
  else if (r > 0) // まだ和に達していない
122
122
 

4

追記のコードの表示を Arrays を使うものに変更

2021/08/10 21:34

投稿

kazuma-s
kazuma-s

スコア8224

test CHANGED
@@ -90,15 +90,19 @@
90
90
 
91
91
  ```Java
92
92
 
93
+ import java.util.Arrays;
94
+
95
+
96
+
93
97
  class Main {
94
98
 
95
99
  public static void main(String []args){
96
100
 
97
- for (String s : args) {
101
+ for (int i = 0; i < args.length; i++) {
98
102
 
99
- int n = Integer.parseInt(s);
103
+ int n = Integer.parseInt(args[i]);
100
104
 
101
- System.out.println(n);
105
+ if (i > 0) System.out.println();
102
106
 
103
107
  gen(new int[n], 0, n, n);
104
108
 
@@ -110,15 +114,9 @@
110
114
 
111
115
  static void gen(int[] a, int i, int j, int r) {
112
116
 
113
- if (r == 0) { // 和ができたので表示
117
+ if (r == 0) // 和ができたので表示
114
118
 
115
- String s = "";
116
-
117
- for (j = 0; j < i; j++) s += " " + a[j];
118
-
119
- System.out.println(s);
119
+ System.out.println(Arrays.toString(Arrays.copyOfRange(a, 0, i)));
120
-
121
- }
122
120
 
123
121
  else if (r > 0) // まだ和に達していない
124
122
 
@@ -142,24 +140,22 @@
142
140
 
143
141
  $ java Main 3 4
144
142
 
145
- 3
143
+ [3]
146
144
 
147
- 3
145
+ [2, 1]
148
146
 
149
- 2 1
147
+ [1, 1, 1]
150
148
 
151
- 1 1 1
152
149
 
153
- 4
154
150
 
155
- 4
151
+ [4]
156
152
 
157
- 3 1
153
+ [3, 1]
158
154
 
159
- 2 2
155
+ [2, 2]
160
156
 
161
- 2 1 1
157
+ [2, 1, 1]
162
158
 
163
- 1 1 1 1
159
+ [1, 1, 1, 1]
164
160
 
165
161
  ```

3

追記

2021/08/10 21:18

投稿

kazuma-s
kazuma-s

スコア8224

test CHANGED
@@ -81,3 +81,85 @@
81
81
  }
82
82
 
83
83
  ```
84
+
85
+ **追記**
86
+
87
+ gen を static にして、Sumクラスを使わずに、
88
+
89
+ さらに、和を引数で与えるようにしてみました。
90
+
91
+ ```Java
92
+
93
+ class Main {
94
+
95
+ public static void main(String []args){
96
+
97
+ for (String s : args) {
98
+
99
+ int n = Integer.parseInt(s);
100
+
101
+ System.out.println(n);
102
+
103
+ gen(new int[n], 0, n, n);
104
+
105
+ }
106
+
107
+ }
108
+
109
+
110
+
111
+ static void gen(int[] a, int i, int j, int r) {
112
+
113
+ if (r == 0) { // 和ができたので表示
114
+
115
+ String s = "";
116
+
117
+ for (j = 0; j < i; j++) s += " " + a[j];
118
+
119
+ System.out.println(s);
120
+
121
+ }
122
+
123
+ else if (r > 0) // まだ和に達していない
124
+
125
+ for (; j > 0; j--) {
126
+
127
+ a[i] = j;
128
+
129
+ gen(a, i + 1, j, r - j); // 再帰呼出し
130
+
131
+ }
132
+
133
+ }
134
+
135
+ }
136
+
137
+ ```
138
+
139
+ 実行例
140
+
141
+ ```text
142
+
143
+ $ java Main 3 4
144
+
145
+ 3
146
+
147
+ 3
148
+
149
+ 2 1
150
+
151
+ 1 1 1
152
+
153
+ 4
154
+
155
+ 4
156
+
157
+ 3 1
158
+
159
+ 2 2
160
+
161
+ 2 1 1
162
+
163
+ 1 1 1 1
164
+
165
+ ```

2

説明の修正 (0 -> 1)

2021/08/10 20:36

投稿

kazuma-s
kazuma-s

スコア8224

test CHANGED
@@ -2,7 +2,7 @@
2
2
 
3
3
  大きさ n の配列を用意して、大きい数から詰め込んで行くことにします。
4
4
 
5
- まだ和に達していなければ、左側以下の値を大きいものから順に 0 になるまで
5
+ まだ和に達していなければ、左側以下の値を大きいものから順に 1 になるまで
6
6
 
7
7
  詰め込んで、次に行くというのを繰り返せばよいでしょう。
8
8
 

1

コードの修正

2021/08/10 14:47

投稿

kazuma-s
kazuma-s

スコア8224

test CHANGED
@@ -42,13 +42,11 @@
42
42
 
43
43
  class Sum {
44
44
 
45
- int n, a[];
45
+ int a[];
46
46
 
47
47
 
48
48
 
49
49
  Sum(int n) {
50
-
51
- this.n = n;
52
50
 
53
51
  a = new int[n];
54
52
 
@@ -68,9 +66,9 @@
68
66
 
69
67
  }
70
68
 
71
- else if (r > 0 && i < n) // まだ和に達していない
69
+ else if (r > 0) // まだ和に達していない
72
70
 
73
- for (int j = k; j >= 0; j--) {
71
+ for (int j = k; j > 0; j--) {
74
72
 
75
73
  a[i] = j;
76
74