再帰関数入門・全探索編

ビット全探索でやった内容（ビット全探索 - Java初心者の競技プログラミング日記）を、
再帰関数でもやってみようという試み。

import java.util.*;
import static java.lang.System.*;

public class Test {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		char[] ar = {'a','b','c'};
		rec("-",0,ar);
	}

	static void rec (String s, int n, char[] ar) {
		if (n==ar.length) {out.println(s);}
		else {
			rec(s,n+1,ar);
			rec(s+ar[n],n+1,ar);
		}
	}
}

/*出力

-
-c
-b
-bc
-a
-ac
-ab
-abc

*/

n=0のとき、

・rec("-", 1, ar)　ar[0]='a'を加えない場合
・rec("-a", 1, ar)　'a'を加える場合

というふうに処理される。

以降、n=1のときはbを加えるか加えないかの処理がなされ、n=2のときには同様にcの処理がなされる。n=3（集合の要素数と同値）のときに出力。

ビット全探索と再帰、どちらを使うかは問題によると思う。