题目.png

题意：幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。
说明：解集不能包含重复的子集。

解法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;
        }
    }
}