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

216.组合总和III

public class Solution {
    List<IList<int>> result=new List<IList<int>>();
    List<int> path=new List<int>();
    int sum=0;
    public IList<IList<int>> CombinationSum3(int k, int n) {
        backtracking(n,k,1);
        return result;
    }
    public void backtracking(int n,int k,int startIndex)
    {
        sum=path.Sum();
        if(sum>n)
        {
            return;
        }
        if(path.Count==k&&sum==n)
        {
            result.Add(new List<int>(path));
            return;
        }
        for(int i=startIndex;i<=9-(k-path.Count)+1;i++)
        {
            path.Add(i);
            backtracking(n,k,i+1);
            path.RemoveAt(path.Count-1);
        }
    }
}

和普通的相比只需要限定一个和值条件就行，因为都只能用一次，所以StartIndex和普通版本一样。

17.电话号码的字母组合

public class Solution {
    List<string> result=new List<string>();
    public IList<string> LetterCombinations(string digits) {
        if(digits==null||digits.Length==0)
        {
            return result;
        }
        string [] str={"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        backtracking(digits,str,0);
        return  result;
    }
    StringBuilder temp=new StringBuilder();
    public void backtracking(string digits,string[] str,int starIndex)
    {
        if(starIndex==digits.Length)
        {
            result.Add(temp.ToString());
            return;
        }
        string st=str[digits[starIndex]-'0'];
        for(int i=0;i<st.Length;i++)
        {
            temp.Append(st[i]);
            backtracking(digits,str,starIndex+1);
            temp.Remove(temp.Length-1,1);
        }
    }
}

需要将每一个按键对应的字母转换成String数组储存，然后返回条件是Startindex走完了输入的字符串长度，每一个都要减去零的Ascii码做一个转换才行，其余处理和普通回溯一样。