递归算法学习v2.2

1. 46. 全排列

2. 

class Solution {
    List<List<Integer>> ret;
    List<Integer> path;
    boolean[] check;
    public List<List<Integer>> permute(int[] nums) {

        ret = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[nums.length];

        dfs(nums);
        return ret;
    }
    public void dfs(int[] nums){
        if(path.size() == nums.length){
            ret.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0;i < nums.length;i++){
            if(check[i] == false){
                path.add(nums[i]);
                check[i] = true;
                dfs(nums);
                check[i] = false;
                path.remove(path.size()-1);
            }
        }
    }
}

1. 78. 子集

法一：盯着数组中某一位置的元素，考虑该元素选不选·0

class Solution {
    List<List<Integer>> ret;
    List<Integer> path;
    public List<List<Integer>> subsets(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        dfs(nums,0);
        return ret;
    }
    public void dfs(int[] nums,int pos){
        if(pos == nums.length){
            ret.add(new ArrayList(path));
            return;
        }
        path.add(nums[pos]);
        dfs(nums,pos+1);
        path.remove(path.size()-1);
        dfs(nums,pos+1);
    }
}

法二：根据选择几个数来进行编写

class Solution {
    List<List<Integer>> ret;
    List<Integer> path;
    public List<List<Integer>> subsets(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        dfs(nums,0);
        return ret;
    }
    public void dfs(int[] nums,int pos){
       ret.add(new ArrayList<>(path));
       for(int i = pos;i<nums.length;i++){
        path.add(nums[i]);
        dfs(nums,i+1);
        path.remove(path.size()-1);
    
       }
    }
}

1. 1863. 找出所有子集的异或总和再求和

异或：两个输入不同时输出为1，反之输出为0； 

class Solution {
    int path;
    int sum;
    public int subsetXORSum(int[] nums) {
        dfs(nums,0);
        return sum;
    }

    public void dfs(int[] nums,int pos){
        sum += path;
        for(int  i = pos;i <nums.length;i++){
            path ^= nums[i];
            dfs(nums,i+1);
             path ^= nums[i];
        }
    }
}

1. 47. 全排列 II

class Solution {
    List<List<Integer>> ret;
    List<Integer> path;
    boolean[] check;
    public List<List<Integer>> permute(int[] nums) {

        ret = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums,0);
        return ret;
    }
    public void dfs(int[] nums, int pose){
        if(pose == nums.length){
            ret.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0;i < nums.length;i++){
            if(check[i] == true || (i != 0 && nums[i] == nums[i-1] && check[i-1] == false)){
               continue;
               }
                path.add(nums[i]);
                check[i] = true;
                dfs(nums,pose+1);
                check[i] = false;
                path.remove(path.size()-1);
            
        }
    }
}

1. 17. 电话号码的字母组合

 1、数字和字符的关系

2->a,b,c;

3->d,e,f;

使用字符串数组，下标为2的位置存a,b,c。

class Solution {
    String[] hash = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    List<String> ret;
    StringBuffer path;
    public List<String> letterCombinations(String digits) {
        ret = new ArrayList<>();
        path = new StringBuffer();

        if(digits.length() == 0){
            return ret;
        }
        dfs(digits,0);
        return ret;
    }
    public void dfs(String digits,int pos){
        if(pos == digits.length()){
            ret.add(path.toString());
            return;
        }
        String cur = hash[digits.charAt(pos)-'0'];
        for(int i = 0;i<cur.length();i++){
            path.append(cur.charAt(i));
            dfs(digits,pos+1);
            path.deleteCharAt(path.length()-1);
        }
    }
}

  括号生成

有效的括号组合：

1、（的数量=）的数量

2、从头开始的任何一个子串，（的当前数量大于）的数量

class Solution {
    int left,right,n;
    StringBuffer path;
    List<String> ret;
    public List<String> generateParenthesis(int n1) {
        n = n1;
        path = new StringBuffer();
        ret = new ArrayList<>();
        dfs();
        return ret;
    }
    public void dfs(){
        if(right == n){
            ret.add(path.toString());
            return;
        }
        if(left < n){
            path.append('(');
            left++;
            dfs();
            path.deleteCharAt(path.length()-1);
            left--;
        }
        if(right < left){
            path.append(')');
            right++;
            dfs();
            path.deleteCharAt(path.length()-1);
            right--;
        }
    }
}

  组合

class Solution {
    List<List<Integer>> ret;
    List<Integer> path;
    int n ,k;
    public List<List<Integer>> combine(int n1, int k1) {
        n = n1;k = k1;
        path = new ArrayList<>();
        ret = new ArrayList<>();
        dfs(1);
        return ret;
    }
    public void dfs(int status){
        if(path.size() == k){
            ret.add(new ArrayList<>(path));
            return;
        }
        for(int i = status;i<=n;i++){
            path.add(i);
            dfs(i+1);
            path.remove(path.size()-1);
        }

    }
}

 ps:谢谢观看！