產生N個01的組合
輸入n為3
產生出
000
001
010
011
100
101
110
111
這個程式的時間複雜度是 O(2^n)，因為每一個位元都有兩種可能 (0 或 1)，所以總共會產生 2^n 種不同的二進位字串。而空間複雜度是 O(n)，因為遞迴過程中每一個呼叫會創造一個新的字串，字串的最大長度為 n。因此，總共需要 O(n)的空間來存儲每個遞迴呼叫的輸入參數和產生的字串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class GenerateBinaryNum {
public static void main(String[] args) {
GenerateBinaryNum ge = new GenerateBinaryNum();
ge.generate(3, "");
}
private void generate(int n, String track) {
if(n == 0) {
System.out.println(track);
return;
}
for(int i = 0; i < 2; i++) {
track += i;
generate(n - 1, track);
track = track.substring(0,track.length()-1);
}
}
}
若要產生0-9的組合，二個數字，修改條件 ge.generate(2, “”); for(int i = 0; i < 10; i++) {
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package com.test;
public class GenerateBinaryNum {
public static void main(String[] args) {
GenerateBinaryNum ge = new GenerateBinaryNum();
ge.generate(2, "");
}
private void generate(int n, String track) {
if(n == 0) {
System.out.println(track);
return;
}
for(int i = 0; i < 10; i++) {
track += i;
generate(n - 1, track);
track = track.substring(0,track.length()-1);
}
}
}