代码随想录算法训练营第二十五天| 216 组合总合 ||| 17 电话号码的字母组合

216 组合总和 |||

暴力

class Solution {
    List<List<Integer>>res = new ArrayList<>();
    List<Integer>newList = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        soluHelper(1,k,n,0);
        return res;
    }
    private void soluHelper(int num,int k,int n,int sum){
        if(sum > n)return;//减枝操作
        if(newList.size() == k){
            if(sum == n)res.add(new ArrayList(newList));
            return;
        }
        for(int i = num;i <= 9;i++){
            newList.add(i);
            sum += i;
            soluHelper(i + 1,k,n,sum);
            newList.remove(newList.size() - 1);
            sum -= i;
        }
    }
}

时间复杂度O(N × $2^{N}$ )N为集合的大小，本题中为9，一个有 $2^{N}$ 个状态(选择或者不选这个数字)

空间复杂度O(N) newList的空间大小

减枝优化

class Solution {
    List<List<Integer>>res = new ArrayList<>();
    List<Integer>newList = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        soluHelper(1,k,n,0);
        return res;
    }
    private void soluHelper(int num,int k,int n,int sum){
        if(sum > n)return;//减枝操作
        if(newList.size() == k){
            if(sum == n)res.add(new ArrayList(newList));
            return;
        }
        for(int i = num;i <= 9 - (k - newList.size()) + 1;i++){//减枝操作
            newList.add(i);
            sum += i;
            soluHelper(i + 1,k,n,sum);
            newList.remove(newList.size() - 1);
            sum -= i;
        }
    }
}

时间复杂度O(N × $2^{N}$ )N为集合的大小，本题中为9，一个有 $2^{N}$ 个状态(选择或者不选这个数字)

空间复杂度O(N) newList的空间大小

17 电话号码的字母组合

class Solution {
    List<String>res = new ArrayList<>();
    StringBuffer sb = new StringBuffer();
    Map<Integer,String>mp = new HashMap<>();
    String[] strs = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    public List<String> letterCombinations(String digits) {
        if(digits.length() == 0 || digits == null)return res;
        SoluHelper(digits,0);
        return res;
    }
    private void SoluHelper(String digits,int cnt){
        if(cnt == digits.length()){
            res.add(sb.toString());
            return;
        }
        String str = strs[digits.charAt(cnt) - '0'];
        for(int i = 0;i < str.length();i++){
            sb.append(str.charAt(i));
            SoluHelper(digits,cnt + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

时间复杂度O( $3^{N}$ × $4^{M}$ )N是对应三个字母的数字个数,M是对应四个字母的数字个数