题意:幂集。编写一种方法,返回某集合的所有子集。集合中不包含重复的元素。
说明:解集不能包含重复的子集。
解法1:
回溯算法
1.回溯算法的关键,在于递归、复位、结束条件
2.模版代码
private void backtrack("原始参数") {
//终止条件(递归必须要有终止条件)
if ("终止条件") {
//一些逻辑操作(可有可无,视情况而定)
return;
}
for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) {
//一些逻辑操作(可有可无,视情况而定)
//做出选择
//递归
backtrack("新的参数");
//一些逻辑操作(可有可无,视情况而定)
//撤销选择
}
}
解法2:
1.数组遍历的方法
2.每次遍历结果数组,根据当前结果list,然后添加当前元素,加入新的list
image.png
解题遇到的问题
无
后续需要总结学习的知识点
无
##解法1
import java.util.ArrayList;
import java.util.List;
class Solution {
List<List<Integer>> path = new ArrayList<List<Integer>>();
public List<List<Integer>> subsets(int[] nums) {
backtrackSearch(nums, 0, new boolean[nums.length],
new ArrayList<Integer>());
return path;
}
private void backtrackSearch(int[] nums, int current, boolean[] used,
ArrayList<Integer> arrayList) {
if (arrayList.size() <= nums.length) {
path.add(new ArrayList<Integer>(arrayList));
}
if (arrayList.size() >= nums.length) {
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
return;
}
// (i > 0 && !used[i - 1])
used[i] = true;
arrayList.add(nums[i]);
backtrackSearch(nums, i + 1, used, arrayList);
arrayList.remove(arrayList.size() - 1);
used[i] = false;
}
}
}
网友评论