摘要：通用算法思路總結(jié)初始結(jié)果列表?？赡芤獙?shù)集排序，方便處理重復元素的情況。書寫遞歸函數(shù)，先要考慮原點狀況，一般就是考慮什么情況下要將當前結(jié)果添加到結(jié)果列表中。每當一個元素添加到當前結(jié)果中之后，要再調(diào)用遞歸函數(shù)，相當于固定了前綴窮舉后面的變化。
通用算法思路總結(jié)：
初始結(jié)果列表。
可能要將數(shù)集排序，方便處理重復元素的情況。
調(diào)用遞歸函數(shù)。
書寫遞歸函數(shù)，先要考慮原點狀況，一般就是考慮什么情況下要將當前結(jié)果添加到結(jié)果列表中。
for循環(huán)遍歷給定集合所有元素，不同題目區(qū)別在于進行循環(huán)的條件，具體看例子。每當一個元素添加到當前結(jié)果中之后，要再調(diào)用遞歸函數(shù)，相當于固定了前綴窮舉后面的變化。
調(diào)用完之后要將當前結(jié)果中最后一個元素去掉，進行下一個循環(huán)才不會重復。
如果對于遞歸過程不熟悉的，可以用debug模式觀察參數(shù)在遞歸過程中的變化。
舉例包含：
78.Subsets
90.SubsetsII
46.Permuation
77.Combinations
39.Combination Sum
40.Combination Sum II
131.Panlindrome Partitioning
78.Subsets
給一個數(shù)集（無重復數(shù)字），要求列出所有子集。
public class Solution {
List> res;
public List> subsets(int[] nums) {
res = new ArrayList<>();
if(nums.length == 0)
return res;
List temp = new ArrayList<>();
helper(nums,temp,0);
return res;
}
private void helper(int[] nums, List temp,int i) {
res.add(new ArrayList<>(temp));
for(int n = i; n < nums.length;n++){
temp.add(nums[n]);
helper(nums,temp,n+1);
temp.remove(temp.size()-1);
}
}
}
90.SubsetsII
給一個數(shù)集（有重復數(shù)字），要求列出所有子集。
public List> subsetsWithDup(int[] nums) {
List> list = new ArrayList<>();
Arrays.sort(nums);
helper(list, new ArrayList<>(), nums, 0);
return list;
}
private void helper(List> list, List tempList, int [] nums, int start){
list.add(new ArrayList<>(tempList));
for(int i = start; i < nums.length; i++){
if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
tempList.add(nums[i]);
helper(list, tempList, nums, i + 1);
tempList.remove(tempList.size() - 1);
}
}
46.Permuation
給一個數(shù)集（無重復元素），返回所有排列。
public class Solution {
List> result;
public List> permute(int[] nums) {
result = new ArrayList<>();
if(nums.length == 0) return result;
helper(nums,new ArrayList<>());
return result;
}
private void helper(int[] nums,List temp){
if(temp.size() == nums.length)
result.add(new ArrayList<>(temp));
else{
for(int i = 0;i
77.Combinations
給一個正整數(shù)n,要求返回1-n中k（k<=n）個數(shù)所有組合的可能。
public class Solution {
List> ret;
public List> combine(int n, int k) {
ret = new ArrayList<>();
if(n temp = new ArrayList<>();
helper(start,n,k,temp);
return ret;
}
private void helper(int start,int n,int k,List temp){
if(temp.size() == k){
ret.add(new ArrayList(temp));
} else {
for(int i = start;i<=n;i++){
temp.add(i);
helper(i+1,n,k,temp);
temp.remove(temp.size()-1);
}
}
}
}
39.Combination Sum
給一個數(shù)集和一個數(shù)字target，要求返回 用數(shù)集中數(shù)字加和等于target的所有組合 （數(shù)集中的數(shù)可以重復使用）。
public class Solution {
List> result;
public List> combinationSum(int[] candidates, int target) {
result = new ArrayList<>();
Arrays.sort(candidates);
helper(candidates,new ArrayList<>(),target,0);
return result;
}
private void helper(int[] candidates,List temp, int remain,int start){
if(remain == 0) {
result.add(new ArrayList<>(temp));
return;
}
for(int i = start;i < candidates.length && remain >= candidates[i];i++){
int tempRemain = remain - candidates[i];
if(tempRemain == 0 || tempRemain >= candidates[i]){
temp.add(candidates[i]);
//此處用i，因為可以重復使用元素
helper(candidates,temp,tempRemain,i);
temp.remove(temp.size()-1);
}
}
}
}
40.Combination Sum II
給一個數(shù)集和一個數(shù)字target，要求返回 用數(shù)集中數(shù)字加和等于target的所有組合 （數(shù)集中的數(shù)不可以重復使用）。
public class Solution {
List> result;
public List> combinationSum2(int[] candidates, int target) {
result = new ArrayList<>();
Arrays.sort(candidates);
helper(candidates,new ArrayList<>(),0,target);
return result;
}
private void helper(int[] candidates, List temp,int start ,int remain){
if(remain == 0){
result.add(new ArrayList<>(temp));
return;
}
//加入remain判斷條件，跳過不必要的循環(huán)。
for(int i = start; i < candidates.length && remain >= candidates[i];i++){
if(i > start && candidates[i] == candidates[i-1]) continue;
int tempRemain = remain - candidates[i];
if(tempRemain == 0 || tempRemain >= candidates[i]){
temp.add(candidates[i]);
helper(candidates,temp,i+1,tempRemain);
temp.remove(temp.size()-1);
}
}
}
}
131.Panlindrome Partitioning
給定一個回文字符串，要求將其分成多個子字符串，使得每個子字符串都是回文字符串，列出所有劃分可能。
public class Solution {
List> result;
public List> partition(String s) {
result = new ArrayList<>();
helper(new ArrayList<>(),s,0);
return result;
}
private void helper(List temp, String s, int start){
if(start == s.length()){
result.add(new ArrayList<>(temp));
return;
}
for(int i = start; i < s.length();i++){
if(isPanlidrome(s,start,i)){
temp.add(s.substring(start,i+1));
helper(temp,s,i+1);
temp.remove(temp.size()-1);
}
}
}
private boolean isPanlidrome(String s, int low ,int high){
while(low < high)
if(s.charAt(low++) != s.charAt(high--)) return false;
return true;
}
}
如有錯誤，歡迎指出。
ref: general approach for ... problem
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66095.html
