题目
题目链接
题解
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<Integer>> subsets(int[] nums) {
if (nums == null || nums.length == 0) {
return new ArrayList<>(0);
}
// 动态答案解
List<Integer> t = new ArrayList<Integer>(nums.length);
// 答案集合
List<List<Integer>> ans = new ArrayList<>();
dfs(0, nums, t, ans);
return ans;
}
/**
* 递归回溯
* @param cur 指针
* @param nums 传入数组
* @param t 动态答案解（动态调整此数组获得每一步答案）
* @param ans 答案集合
*/
public void dfs(int cur, int[] nums, List<Integer> t, List<List<Integer>> ans) {
// 叶子节点 记录答案
if (cur == nums.length) {
ans.add(new ArrayList<Integer>(t));
return;
}
// 前序遍历节点操作
// 向当前答案中添加元素
t.add(nums[cur]);
// 向左子树延申
dfs(cur + 1, nums, t, ans);
// 中序遍历节点操作
// 该答案已经被记录，删除最后一个元素，本质上跳过了当前cur下标的元素
t.remove(t.size() - 1);
// 向右子树延申
dfs(cur + 1, nums, t, ans);
}
}