2018-11-21 组合排列

image.png

class Solution {
    public List<String> letterCombinations(String digits) {
         List<String> res = new ArrayList();
        String s = "";
        char[] chars = digits.toCharArray();
        if(chars==null || chars.length<=0){
            return res;
        }
       
        doLetterCombinations(res,s,chars,0);
        return res;
    }
    
    public void doLetterCombinations(List<String> res,String s,char[] chars,int start){
        if(start == chars.length){
            res.add(s);
            return;
        }
        char[] c = getChars(chars[start]);
        start += 1;
        for(int i = 0;i<c.length;i++){
            doLetterCombinations(res,s + c[i],chars, start);
        }
    }
    
    public char[] getChars(char c){
        switch(c){
                case '2':return new char[]{'a','b','c'};
                case '3':return new char[]{'d','e','f'};
                case '4':return new char[]{'g','h','i'};
                case '5':return new char[]{'j','k','l'};
                case '6':return new char[]{'m','n','o'};
                case '7':return new char[]{'p','q','r','s'};
                case '8':return new char[]{'t','u','v'};
                case '9':return new char[]{'w','x','y','z'};
        }
        
        return null;
    }
}

image.png

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList();
        StringBuilder sb = new StringBuilder();
        doGenerateParenthesis(res,sb,n,n);
        
        return res;
    }
    
    public void doGenerateParenthesis( List<String> res, StringBuilder sb,int left,int right){
        if(left == 0 && right == 0){
            res.add(sb.toString());
            return;
        }
        if( left < 0 || right <0){
            return;
        }
        
        if(right>left){
            sb.append(')');
            doGenerateParenthesis(res, sb,left,right-1);
            sb.deleteCharAt(sb.length()-1);
        }
        
        sb.append('(');
        doGenerateParenthesis(res, sb,left - 1,right);
        sb.deleteCharAt(sb.length()-1);

    }
}

image.png

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList();
        List<Integer> ele = new ArrayList();
        doCombinationSum(res,ele,target,candidates,0);
        return res;
    }
    
    private void doCombinationSum(List<List<Integer>> res,  List<Integer> ele,int target,int[] candidates,int start){
        if(target == 0){
            res.add(new ArrayList(ele));
            return;
        }
        if(target < 0){
            return;
        }
        
        for(int i=start; i<candidates.length; i++){
            ele.add(candidates[i]);
            doCombinationSum(res, ele,target-candidates[i],candidates,i);
            ele.remove(ele.size()-1);
        }
    }
}

image.png

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList();
        List<Integer> ele = new ArrayList();
        Arrays.sort(candidates);
        docombinationSum2(res,ele,0,target,candidates);
        return res;
    }
    public void docombinationSum2(List res, List ele,int start,int target,int[] candidates){
        if(target == 0){
            res.add(new ArrayList(ele));
            return;
        }
        
        if(target< 0 || start >= candidates.length){
            return;
        }
        
        for(int i = start;i<candidates.length;i++){
            if(i>start && candidates[i] == candidates[i-1]) continue;
            ele.add(candidates[i]);
            docombinationSum2(res, ele,i+1,target - candidates[i],candidates);
            ele.remove(ele.size() - 1);
        }
        
        
    }
}

image.png

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

image.png

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        List<Integer> ele = new ArrayList();
        
        doPerumte(res,ele,nums);
        return res;
    }
    
    public void doPerumte(List<List<Integer>> res,List<Integer> ele ,int[] nums){
        
        if(ele.size() == nums.length){
            res.add(new ArrayList(ele));
            return;
        }
        
        for(int i = 0 ;i < nums.length;i++){
            if(ele.contains(nums[i])){
                continue;
            }
            ele.add(nums[i]);
            doPerumte(res, ele ,nums);
            ele.remove(ele.size()-1);
        }
        
    }
}

image.png

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

image.png

超时

class Solution {
    public int combinationSum4(int[] nums, int target) {
        return doCombinationSum4(nums,target);
    }
    public int doCombinationSum4(int[] nums,int target){
        if(target == 0){
            return 1;
        }
        if(target < 0){
            return 0;
        }
        int sum = 0;
        for(int i=0;i<nums.length;i++){
            sum += doCombinationSum4(nums,target - nums[i]);
        }
        
        return sum;
    }
}