|
6 | 6 | publicclass_77 { |
7 | 7 |
|
8 | 8 | publicstaticclassSolution1 { |
| 9 | +/** |
| 10 | + * I'm glad that I worked this one out completely on my own on 10/11/2021! Enjoy the beauty of backtracking! |
| 11 | + */ |
9 | 12 | publicList<List<Integer>>combine(intn,intk) { |
10 | | -List<List<Integer>>result =newArrayList(); |
11 | | -int[]nums =newint[n]; |
12 | | -for (inti =0;i <n;i++) { |
13 | | -nums[i] =i +1; |
| 13 | +List<List<Integer>>ans =newArrayList<>(); |
| 14 | +for (intnum =1;num <=n -k +1;num++) { |
| 15 | +List<Integer>list =newArrayList<>(); |
| 16 | +list.add(num); |
| 17 | +backtracking(list,k -1,num +1,n,ans); |
14 | 18 | } |
15 | | -backtracking(k,0,nums,newArrayList(),result); |
16 | | -returnresult; |
| 19 | +returnans; |
17 | 20 | } |
18 | 21 |
|
19 | | -voidbacktracking(intk,intstart,int[]nums,List<Integer>curr,List<List<Integer>>result) { |
20 | | -if (curr.size() ==k) { |
21 | | -result.add(newArrayList(curr)); |
22 | | -}elseif (curr.size() <k) { |
23 | | -for (inti =start;i <nums.length;i++) { |
24 | | -curr.add(nums[i]); |
25 | | -backtracking(k,i +1,nums,curr,result); |
26 | | -curr.remove(curr.size() -1); |
27 | | -} |
| 22 | +privatevoidbacktracking(List<Integer>list,intk,intstart,intlimit,List<List<Integer>>ans) { |
| 23 | +if (k ==0) { |
| 24 | +ans.add(newArrayList<>(list)); |
| 25 | +return; |
| 26 | +} |
| 27 | +for (intnum =start;num <=limit;num++) { |
| 28 | +list.add(num); |
| 29 | +backtracking(list,k -1,num +1,limit,ans); |
| 30 | +list.remove(list.size() -1); |
28 | 31 | } |
29 | 32 | } |
30 | 33 | } |
|