排列组合题目小结

排列题目

全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

没有重复元素，比较简单，可以放心的进行交换

class Solution {
    
    public List<List<Integer>> permute(int[] nums) {
    
         public List<List<Integer>> permute(int[] nums) {
    
                 List<List<Integer>> res = new ArrayList<>();
                dfs(nums, res, 0);
                return res;
            }

    private void dfs(int[]nums,List<List<Integer>> res,int index){
    
        if (index==nums.length-1) {
    
            List<Integer> path = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
    
                path.add(nums[i]);
            }
            res.add(path);
        }

        for (int i = index; i < nums.length; i++) {
    
            //排列树进行交换
            swap(nums, index, i);
            dfs(nums,res,index+1);
            swap(nums, index, i);
        }
    }

    private void swap(int[] cs,int i,int j){
    
        int temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }
    }
}

全排列2

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

有重复的数字，进行排列时就会有重复，所以我们再交换的时候加入set，可以抵消这种交换带来的问题

class Solution {
    
    public List<List<Integer>> permuteUnique(int[] nums) {
    
        List<List<Integer>> res = new ArrayList<>();
        dfs(nums, res, 0);
        return res;
    }

    public void dfs(int[]nums,List<List<Integer>> res,int index){
    
        if (index==nums.length-1) {
    
            List<Integer> path = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
    
                path.add(nums[i]);
            }
            res.add(path);
            return;
        }
        Set<Integer> intSet = new HashSet<Integer>();
        for (int i = index; i < nums.length; i++) {
    
            if (i==index || !intSet.contains(nums[i])) {
    
                intSet.add(nums[i]);
                swap(nums, index, i);
                dfs(nums,res,index+1);
                swap(nums, index, i);
            }
        }
    }

    private void swap(int[] cs,int i,int j){
    
        int temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }
}

组合

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

组合问题不存在重复数字，所以不慌，比较简单

class Solution {
    
    int[]nums=null;
    List<List<Integer>> res= new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
    
        nums = new int[n];
        for (int i = 0; i < nums.length; i++) {
    
            nums[i] = i+1;
        }
        List<Integer>path = new ArrayList<>();
        dfs(path,0,k);
        return res;
    }

     public void dfs(List<Integer>path,int index,int k){
    
        if (k==0) {
    
            List<Integer> newpath = new ArrayList<>();
            for (Integer integer : path) {
    
                newpath.add(integer);
            }
            res.add(newpath);
            return;
        }

        for (int i = index; i < nums.length; i++) {
    
            path.add(nums[i]);
            dfs(path,i+1,k-1);
            path.remove(path.size()-1);
        }
    }
}

总结

排列组合问题我总是忘记，所以记录一下，方便下次查看