Climbing Stairs

stair climbing， print out all of possible solutions of the methods to climb a stars, you are allowed climb one or two steps for each time; what is time/space complexity? （use recursion）

这道题难是难在这个ArrayList<String> res是用在argument还是返回值，纠结了好久

Recursion 解法：

 1 package fib;
 2 
 3 import java.util.ArrayList;
 4 
 5 public class climbingstairs {
 6     
 7     public ArrayList<String> climb (int n) {
 8         if (n <= 0) return null;
 9         ArrayList<String> res = new ArrayList<String>();
10         if (n == 1) {
11             res.add("1");
12             return res;
13         }
14         if (n == 2) {
15             res.add("2");
16             res.add("12");
17             return res;
18         }
19         ArrayList<String> former2 =  climb(n-2); 
20         for (String item : former2) {
21             res.add(item+Integer.toString(n));
22         }
23         ArrayList<String> former1 = climb(n-1);
24         for (String item : former1) {
25             res.add(item+Integer.toString(n));
26         }
27         return res;
28     }
29 
30     
31     public static void main(String[] args) {
32         climbingstairs obj = new climbingstairs();
33         ArrayList<String> res = obj.climb(6);
34         for (String item : res) {
35             System.out.println(item);
36         }
37     }
38 
39 }

Sample input : 6

Sample Output:

246
1246
1346
2346
12346
1356
2356
12356
2456
12456
13456
23456
123456

follow up: could you change the algorithm to save space?

这就想到DP，用ArrayList<ArrayList<String>>

 1 import java.util.ArrayList;
 2 
 3 public class climbingstairs {
 4     
 5     public ArrayList<String> climb (int n) {
 6         if (n <= 0) return null;
 7         ArrayList<ArrayList<String>> results = new ArrayList<ArrayList<String>>();
 8         for (int i=1; i<=n; i++) {
 9             results.add(new ArrayList<String>());
10         }
11         if (n >= 1) {
12             results.get(0).add("1");
13         }
14         if (n >= 2) {
15             results.get(1).add("2");
16             results.get(1).add("12");
17         }
18 
19         for (int i=3; i<=n; i++) {
20             ArrayList<String> step = results.get(i-1);
21             ArrayList<String> former2 = results.get(i-3);
22             for (String item : former2) {
23                 step.add(item+Integer.toString(i));
24             }
25             ArrayList<String> former1 = results.get(i-2);
26             for (String item : former1) {
27                 step.add(item+Integer.toString(i));
28             }
29         }
30         return results.get(n-1);
31     }
32 
33     
34     public static void main(String[] args) {
35         climbingstairs obj = new climbingstairs();
36         ArrayList<String> res = obj.climb(5);
37         for (String item : res) {
38             System.out.println(item);
39         }
40     }
41 
42 }