1 Subsets
public List
> subsets(int[] nums) { List
> result = new ArrayList<>(); if (nums.length == 0) { return result; } ArrayList list = new ArrayList<>(); subsetsHelper(nums, 0, list, result); return result; } void subsetsHelper(int[] nums, int pos, List list, List
> result){ result.add(new ArrayList<>(list)); for (int i = pos; i < nums.length; i++) { list.add(nums[i]); subsetsHelper(nums, i + 1, list, result); list.remove(list.size() - 1); } }
2 Subsets II
public List
> subsetsWithDup(int[] nums) { List
> result = new ArrayList<>(); if (nums.length == 0) { return result; } Arrays.sort(nums); ArrayList list = new ArrayList<>(); subsetsHelper(nums, 0, list, result); return result; } void subsetsHelper(int[] nums, int pos, List list, List
> result){ result.add(new ArrayList<>(list)); for (int i = pos; i < nums.length; i++) { if (i > pos && nums[i] == nums[i - 1]){ continue; } list.add(nums[i]); subsetsHelper(nums, i + 1, list, result); list.remove(list.size() - 1); } }
3 Permutations
public List
> permute(int[] nums) { // write your code here List
> res = new ArrayList<>(); if (nums == null || nums.length == 0) { res.add(new ArrayList ()); return res; } List list = new ArrayList<>(); helper(nums, list, res); return res; } void helper(int[] nums, List list, List
> res) { if (list.size() == nums.length) { res.add(new ArrayList<>(list)); return; } for (int i = 0; i < nums.length; i++) { if (list.contains(nums[i])) { continue; } list.add(nums[i]); helper(nums, list, res); list.remove(list.size() - 1); } }
4 Permutations II
public List
> permuteUnique(int[] nums) { // Write your code here List
> result = new ArrayList<>(); if (nums == null || nums.length == 0) { result.add(new ArrayList ()); return result; } Arrays.sort(nums); List list = new ArrayList<>(); boolean[] used = new boolean[nums.length]; helper(nums, list, used, result); return result; } void helper(int[] nums, List list, boolean[] used, List
> result) { if (list.size() == nums.length) { result.add(new ArrayList<>(list)); return; } for (int i = 0; i < nums.length; i++) { if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) { continue; } used[i] = true; list.add(nums[i]); helper(nums, list, used, result); used[i] = false; list.remove(list.size() - 1); } }
5 Combination Sum 可以有重复
public ArrayList> combinationSum(int[] candidates, int target) { ArrayList > res = new ArrayList >(); if (candidates == null || candidates.length == 0) { return res; } Arrays.sort(candidates); helper(candidates, 0, target, new ArrayList (), res); return res; } private void helper(int[] candidates, int start, int target, ArrayList item, ArrayList > res) { // TODO Auto-generated method stub if (target < 0) { return; } if (target == 0) { res.add(new ArrayList<>(item)); return; } for (int i = start; i < candidates.length; i++) { if (i > 0 && candidates[i] == candidates[i - 1]) { continue; } item.add(candidates[i]); helper(candidates, i, target - candidates[i], item, res); item.remove(item.size() - 1); } }
6 Combination Sum 不可以有重复
public List
> combinationSum2(int[] nums, int target) { List
> list = new ArrayList<>(); Arrays.sort(nums); backtrack(list, new ArrayList<>(), nums, target, 0); return list; }private void backtrack(List
> list, List tempList, int [] nums, int remain, int start){ if(remain < 0) return; else if(remain == 0) list.add(new ArrayList<>(tempList)); else{ for(int i = start; i < nums.length; i++){ if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates tempList.add(nums[i]); backtrack(list, tempList, nums, remain - nums[i], i + 1); tempList.remove(tempList.size() - 1); } }}
7 Palindrome Partitioning
public class Solution { public List > partition(String s) { List > res = new ArrayList<>(); if (s.length() == 0) return res; dfs(s, 0, new ArrayList (), res); return res; } public void dfs(String s, int index, ArrayList item, List > res){ if (s.length() == index) { res.add(new ArrayList<>(item)); return; } for (int i = index; i < s.length(); i++){ if (isP(s, index, i)){ item.add(s.substring(index, i + 1)); dfs(s, i + 1, item, res); item.remove(item.size() - 1); } } } public boolean isP(String s, int l, int r){ while (l < r) { if (s.charAt(l) != s.charAt(r)){ return false; } l++;r--; } return true; }}