排列、组合、子集问题

求子集

解法一：

subset([1,2,3]) - subset([1,2])= [3],[1,3],[2,3],[1,2,3]

而这个结果，就是把 sebset([1,2]) 的结果中每个集合再添加上 3。

换句话说，如果 A = subset([1,2]) ，那么：

subset([1,2,3])= A + [A[i].add(3) for i = 1..len(A)]

这就是一个典型的递归结构嘛，[1,2,3] 的子集可以由 [1,2] 追加得出，[1,2] 的子集可以由 [1] 追加得出，base case 显然就是当输入集合为空集时，输出子集也就是一个空集。

递归实现：

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        // 添加空子集
        ans.add(new ArrayList<>());
        // 当前索引
        int idx = 0;
        while(idx<nums.length){
            // 要增加的值
            int num = nums[idx];
            // 新建子序列
            List<List<Integer>> subList = new ArrayList<>();
            // 深拷贝
            for(List<Integer> item: ans){
                subList.add(new ArrayList<>(item));
            }
            // 往子序列中增加值，并添加到结果中
            for(List<Integer> item :subList){
                item.add(num);
                ans.add(item);
            }
            // 索引增加
            idx++;
        }
        return ans;
    }
}

回溯实现：

class Solution {
    // 存放结果
    List<List<Integer>> ans = new ArrayList<>();
    // 存放路径
    LinkedList<Integer> track = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backtrack(nums,0,track);
        return ans;
    }
    public void backtrack(int[] nums,int start,LinkedList<Integer> track){
        // 添加结果
        ans.add(new ArrayList<>(track));
        // 寻找下个值
        for(int i = start;i<nums.length;i++){
            // 延长路径
            track.add(nums[i]);
            // 继续回溯
            backtrack(nums,i+1,track);
            // 缩短路径
            track.remove(track.size()-1);
        }
    }
}

组合

和计算子集的差不多，区别在于，更新 res 的地方是树的底端。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        if(n<=0||k<=0) return res;
        backtrack(n,k,1);
        return res;
    }
    public void backtrack(int n,int k,int start){
        if(k == path.size()){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = start;i<=n;i++){
            path.add(i);
            backtrack(n,k,i+1);
            path.remove(path.size()-1);
        }
    }
}

全排列

排列问题每次通过 contains 方法来排除在 track 中已经选择过的数字；而组合问题通过传入一个 start 参数，来排除 start 索引之前的数字。

class Solution {
	List<List<Integer>> res = new LinkedList<>();

	/* 主函数，输入一组不重复的数字，返回它们的全排列 */
	List<List<Integer>> permute(int[] nums) {
		// 记录「路径」
		LinkedList<Integer> track = new LinkedList<>();
		backtrack(nums, track);
		return res;
	}

	void backtrack(int[] nums, LinkedList<Integer> track) {
		// 触发结束条件
		if (track.size() == nums.length) {
			res.add(new LinkedList(track));
			return;
		}

		for (int i = 0; i < nums.length; i++) {
			// 排除不合法的选择
			if (track.contains(nums[i]))
				continue;
			// 做选择
			track.add(nums[i]);
			// 进入下一层决策树
			backtrack(nums, track);
			// 取消选择
			track.removeLast();
		}
	} 
}

排列、组合、子集问题 #

求子集 #

组合 #

全排列 #

排列、组合、子集问题

求子集

组合

全排列