代码随想录 day27 39. 组合总和 | 40.组合总和II

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        helper(res, new ArrayList<>(), candidates, target, 0, 0);
        return res;
    }
    private void helper(List<List<Integer>>  res, List<Integer> path, int[] candidates, int target,int sum, int idx) {
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = idx; i < candidates.length; i++) {
            if (sum + candidates[i] > target) break;
            path.add(candidates[i]);
            helper(res, path, candidates, target ,sum + candidates[i], i);
            path.remove(path.size() - 1);
        }
    }
}

40. 组合总和 II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates); 
        helper(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }

    private void helper(List<List<Integer>> result, List<Integer> cur, int[] candidates, int target, int idx) {
        if (target < 0) return;
        if (target == 0) {
            result.add(new ArrayList<>(cur));
            return;
        }

        for (int i = idx; i < candidates.length; i++) {
            if (i > idx && candidates[i] == candidates[i - 1]) {
                continue;
            }
            cur.add(candidates[i]);
            helper(result,cur,candidates,target - candidates[i],i+1);
            cur.remove(cur.size() - 1);
        }
    }
}

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

class Solution {
    List<List<String>> lists = new ArrayList<>();
    Deque<String> deque = new LinkedList<>();
    public List<List<String>> partition(String s) {
        helper(s, 0);
        return lists;
    }

    private void helper(String s, int idx) {
        if (idx >= s.length()) {
            lists.add(new ArrayList(deque));
            return;
        }
        
        for (int i = idx; i < s.length(); i++) {
            //如果是回文子串，则记录
            if (isPalindrome(s, idx, i)) {
                String str = s.substring(idx, i + 1);
                deque.addLast(str);
            } else {
                continue;
            }
            //起始位置后移，保证不重复
            helper(s, i + 1);
            deque.removeLast();
        }
    }

    private boolean isPalindrome(String s, int startIdx, int endIdx) {
        for (int i = startIdx, j = endIdx; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}

526互联

代码随想录 day27 39. 组合总和 | 40.组合总和II | 131.分割回文串