DFS排序类

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> results = new ArrayList<>();
    if (nums == null || nums.length == 0) {
        return results;
    }

    dfs(nums, new boolean[nums.length], new ArrayLisy<Integer>(), results);
    
    return results;
}

// 1. 递归的定义
public void dfs(
	int[] nums,
    // int index,
    boolean[] visited,
    List<Integer> permutation,
    List<List<Integer>> results
) {
    // 3. 递归的出口
    if (permutation.size() == nums.length) {
        // 深拷贝
        results.add(new ArrayList<Integer>(permutation));
        return;
    }
    
    // 2. 递归的拆解
    for (int i = 0; i < nums.length; i++) {
        if (visited[i]) {
            continue;
        }
        
        permutation.add(nums[index]);
        visited[i] = true;
        dfs(nums, visited, subset, result);
        permutation.remove(subset.size() - 1);
        visited[i] = false;
    }
}

时间复杂度：

n!*n

组合数*每个组合构建时间

实现二，通用性更强，每一个节点都是结果（和全排列的代码也很像）

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> results = new ArrayList<>();
    if (nums == null || nums.length == 0) {
        return results;
    }
    Arrays.sort(nums);
    dfs(nums, 0, new ArrayLisy<Integer>(), results);
    return results;
}

// 1. 递归的定义
public void dfs(
	int[] nums,
    int startIndex,
    List<Integer> subset,
    List<List<Integer>> results
) {
    results.add(new ArrayList<Integer>(subset));
	
    // 2. 递归的拆解，结合这个循环的终止条件也作为递归的出口
    for (int i = startIndex; i < nums.length; i++) {
        subset.add(nums[i]);
        dfs(nums, i + 1, subset, result);
        subset.remove(subset.size() - 1);
    }
}