77.组合

class Solution {List<List<Integer>> res = new ArrayList();Deque<Integer> path = new ArrayDeque();public List<List<Integer>> combine(int n, int k) {combineHelper(n, k, 1);return res;}private void combineHelper(int n, int k, int startIndex) {if (path.size() == k) {res.add(new ArrayList<>(path));return;}for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {path.addFirst(i);combineHelper(n, k, i + 1);path.removeFirst();}}
}

216.组合总和III

class Solution {List<List<Integer>> res = new ArrayList();Deque<Integer> path = new ArrayDeque();int sum = 0;public List<List<Integer>> combinationSum3(int k, int n) {combinationSum3Helper(k, n, 1);return res;}private void combinationSum3Helper(int k, int n, int startIndex) {if (path.size() == k) {if (sum == n) {res.add(new ArrayList<>(path));}return;}for (int i = startIndex; i <= 9; i++) {if (sum + i > n) break;sum += i;path.addFirst(i);combinationSum3Helper(k, n, i + 1);path.removeFirst();sum -= i;}}
}

39. 组合总和

class Solution {List<List<Integer>> res = new ArrayList();Deque<Integer> path = new ArrayDeque();int sum = 0;public List<List<Integer>> combinationSum(int[] candidates, int target) {if (candidates == null || candidates.length == 0) return res;Arrays.sort(candidates);combinationSumHelper(candidates, target, 0);return res;}private void combinationSumHelper(int[] candidates, int target, int startIndex) {if (sum == target) {res.add(new ArrayList<>(path));return;}for (int i = startIndex; i < candidates.length; i++) {if (sum + candidates[i] > target) break;sum += candidates[i];path.addFirst(candidates[i]);combinationSumHelper(candidates, target, i);path.removeFirst();sum -= candidates[i];}}
}

40.组合总和II

class Solution {List<List<Integer>> res = new ArrayList();Deque<Integer> path = new ArrayDeque();int sum = 0;public List<List<Integer>> combinationSum2(int[] candidates, int target) {if (candidates == null || candidates.length == 0) return res;Arrays.sort(candidates);combinationSum2Helper(candidates, target, 0);return res;}private void combinationSum2Helper(int[] candidates, int target, int startIndex) {if (sum == target) {res.add(new ArrayList<>(path));return;}for (int i = startIndex; i < candidates.length; i++) {if (i > startIndex && candidates[i] == candidates[i - 1]) continue;if (sum + candidates[i] > target) break;sum += candidates[i];path.addFirst(candidates[i]);combinationSum2Helper(candidates, target, i + 1);path.removeFirst();sum -= candidates[i];}}
}

17.电话号码的字母组合

class Solution {List<String> res = new ArrayList();String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};StringBuilder builder = new StringBuilder();public List<String> letterCombinations(String digits) {if (digits == null || digits.length() == 0) {return res;}letterCombinationsHelper(digits, 0);return res;}private void letterCombinationsHelper(String digits, int index) {if (index == digits.length()) {res.add(builder.toString());return;}String s = numString[digits.charAt(index) - '0'];for (int i = 0; i < s.length(); i++) {builder.append(s.charAt(i));letterCombinationsHelper(digits, index + 1);builder.deleteCharAt(builder.length() - 1);}}
}

78.子集

class Solution {List<List<Integer>> res = new ArrayList();Deque<Integer> path = new ArrayDeque();public List<List<Integer>> subsets(int[] nums) {subsetsHelper(nums, 0);return res;}private void subsetsHelper(int[] nums, int startIndex) {res.add(new ArrayList<>(path));for (int i = startIndex; i < nums.length; i++) {path.addFirst(nums[i]);subsetsHelper(nums, i + 1);path.removeFirst();}}
}