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;
}
}
网友评论