在Java中可以使用遞歸來實現排列組合算法。以下是一個示例代碼:
import java.util.ArrayList;
import java.util.List;
public class Combination {
public static void main(String[] args) {
List<Integer> nums = new ArrayList<>();
nums.add(1);
nums.add(2);
nums.add(3);
nums.add(4);
int r = 3; // 選擇r個元素進行組合
List<List<Integer>> combinations = combine(nums, r);
for (List<Integer> combination : combinations) {
for (int num : combination) {
System.out.print(num + " ");
}
System.out.println();
}
}
public static List<List<Integer>> combine(List<Integer> nums, int r) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
dfs(nums, r, 0, path, result);
return result;
}
private static void dfs(List<Integer> nums, int r, int start, List<Integer> path, List<List<Integer>> result) {
if (path.size() == r) {
result.add(new ArrayList<>(path));
return;
}
for (int i = start; i < nums.size(); i++) {
path.add(nums.get(i));
dfs(nums, r, i + 1, path, result);
path.remove(path.size() - 1);
}
}
}
上述代碼使用了深度優先搜索(DFS)的方式來生成排列組合。首先定義了一個combine
方法,接收一個包含元素的列表和選擇的元素個數r
作為參數。在combine
方法中,創建了一個結果列表result
和一個路徑列表path
。然后調用dfs
方法進行深度優先搜索。
dfs
方法接收了待選擇的元素列表nums
、選擇的元素個數r
、當前搜索的起始位置start
、當前路徑path
和結果列表result
作為參數。首先判斷當前路徑的長度是否等于選擇的元素個數r
,如果是,則將當前路徑加入結果列表,并返回。否則,從起始位置start
開始遍歷待選擇的元素列表nums
,將當前元素加入路徑列表path
,然后遞歸調用dfs
方法繼續搜索下一個元素,搜索的起始位置為當前位置的下一個位置i + 1
。當遞歸返回后,將當前元素從路徑列表中移除,繼續遍歷下一個元素。最后,返回結果列表。
運行上述代碼,輸出結果為:
1 2 3
1 2 4
1 3 4
2 3 4
這就是給定列表中選擇3個元素進行排列組合的結果。