子集
例：[1,2,3] 的所有子集
結(jié)果 []烙心，[1]膜廊，[1,2]，[1,2,3]淫茵，[1,3]爪瓜，[2]，[2,3]匙瘪，[3]
算法原理描述
條件：集合中的元素不可重復(fù)铆铆，可按任意順序排列
算法過(guò)程：在第一個(gè)位置枚舉集合中的所有元素，在每個(gè)元素的下一位置枚舉所有在它之后的元素丹喻，之后表示在集合中的順序薄货。在每加入一個(gè)新元素時(shí)，形成一個(gè)結(jié)果碍论。在當(dāng)前位置枚舉完所有可以枚舉的元素后谅猾，返回上一層。
算法過(guò)程舉例：
[]????????????空集也算一個(gè)子集
[1],?????????在第一個(gè)位置枚舉集合中的所有元素，即1税娜，2先煎，3，第一次是 1
[1,2],??????在第二個(gè)位置枚舉集合中 1 之后的元素巧涧，即是 2 和 3薯蝎，第一次是 2
[1,2,3],???在第三個(gè)位置枚舉集合中 2 之后的元素，只有 3 谤绳，枚舉完就返回第二個(gè)位置
[1,3],??????在第二個(gè)位置枚舉集合中 1 之后的元素占锯，第二次是 3，枚舉完返回第一個(gè)位置
[2],?????????在第一個(gè)位置枚舉集合中的所有元素缩筛，第二次是 2
[2,3],??????在第二個(gè)位置枚舉集合中 2 之后的元素消略，只有 3，枚舉完返回第一個(gè)位置
[3]??????????在第一個(gè)位置枚舉集合中的所有元素瞎抛，第三次是 3艺演，枚舉完，結(jié)束
算法的動(dòng)態(tài)圖演示
算法代碼
List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
backtrack(list, new ArrayList<>(), nums, 0);
return list;
}
void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
list.add(new ArrayList<>(tempList));
for(int i = start; i < nums.length; i++){
tempList.add(nums[i]);
backtrack(list, tempList, nums, i + 1);
tempList.remove(tempList.size() - 1);
}
}
看明白第一個(gè)桐臊，下面兩個(gè)就容易理解了
?
排列
例：[1,2,3] 的所有排列情況
結(jié)果：[1,2,3]胎撤，[1,3,2]，[2,1,3]断凶，[2,3,1]伤提，[3,1,2]，[3,2,1]
算法原理描述
條件：集合中的元素不可重復(fù)认烁，可按任意順序排列
算法過(guò)程：在第一個(gè)位置枚舉集合中的所有元素肿男，在每個(gè)元素的下一位置枚舉所有集合中且在前面的位置沒(méi)有出現(xiàn)過(guò)的元素。在元素?cái)?shù)量與給出集合的元素?cái)?shù)量相等時(shí)却嗡，形成一個(gè)結(jié)果舶沛。在當(dāng)前位置枚舉完所有可以枚舉的元素后，返回上一層窗价。
算法代碼
List<List<Integer>> permute(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
backtrack(list, new ArrayList<>(), nums);
return list;
}
void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
if(tempList.size() == nums.length){
list.add(new ArrayList<>(tempList));
} else {
for(int i = 0; i < nums.length; i++) {
if(tempList.contains(nums[i])) continue;
tempList.add(nums[i]);
backtrack(list, tempList, nums);
tempList.remove(tempList.size() - 1);
}
}
}
?
組合
例：在 [2,3,5] 中選任意元素 (可以重復(fù)選擇同一個(gè)) 如庭，之和為 8
結(jié)果：[2,2,2,2]，[2,3,3]舌镶，[3,5]
算法原理描述
條件：集合中的元素不可重復(fù)柱彻，按數(shù)字順序從小到大排列
算法過(guò)程：在第一個(gè)位置枚舉集合中的所有元素，在每個(gè)元素的下一位置枚舉所有在它之后的元素 (包括它)餐胀，之后表示在集合中的順序哟楷。在所有元素的和等于 8 時(shí)，形成一個(gè)結(jié)果否灾。在所有元素的和大于 8 時(shí)卖擅，返回上一層。
算法代碼
List<List<Integer>> combinationSum(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, target, 0);
return list;
}
void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
if(remain < 0) return;
else if(remain == 0) list.add(new ArrayList<>(tempList));
else{
for(int i = start; i < nums.length; i++){
tempList.add(nums[i]);
backtrack(list, tempList, nums, remain - nums[i], i);
tempList.remove(tempList.size() - 1);
}
}
}
