回溯法

• OI Wiki: https://oi-wiki.org/search/backtracking/

题目	难度
78. 子集	中等
90. 子集 II	中等

定义

backtracking

78. 子集

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Solution78 {
    private int[] nums;
    private LinkedList<Integer> subset;
    private List<List<Integer>> subsetList;

    public List<List<Integer>> subsets(int[] nums) {
        this.nums = nums;
        subset = new LinkedList<>();
        subsetList = new ArrayList<>();
        dfs(0);
        return subsetList;
    }

    private void dfs(int i) {
        if (i == nums.length) {
            subsetList.add(new ArrayList<>(subset));
            return;
        }
        // 不选
        dfs(i + 1);
        // 选
        subset.add(nums[i]);
        dfs(i + 1);
        subset.removeLast();
    }
}

90. 子集 II

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Solution90 {
    private int[] nums;
    private LinkedList<Integer> subset;
    private List<List<Integer>> subsetList;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        this.nums = nums;
        subset = new LinkedList<>();
        subsetList = new ArrayList<>();
        dfs(0);
        return subsetList;
    }

    private void dfs(int i) {
        if (i == nums.length) {
            subsetList.add(new ArrayList<>(subset));
            return;
        }
        // 不选
        dfs(getNext(i));
        // 选
        subset.add(nums[i]);
        dfs(i + 1);
        subset.removeLast();
    }

    private int getNext(int i) {
        int next = i;
        while (next < nums.length && nums[next] == nums[i]) {
            next++;
        }
        return next;
    }
}

（全文完）