排列组合题目小结

心已赠人 2023-02-20 06:19 12阅读 0赞

# 排列组合题目小结 #

## 排列题目 ##

### 全排列 ###

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

**示例:**

> **输入:** \[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);
            }
        }
    }

## 总结 ##

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