题目描述（中等难度）

和上一道题非常像了，区别在于这里给的数组中有重复的数字，每个数字只能使用一次，然后同样是给出所有和等于 target 的情况。

解法一回溯法

只需要在上题的基础上改一下就行了。直接看代码吧。 1. public List> combinationSum2(int[] candidates, int target) { 2. List> ans = new ArrayList<>(); 3. getAnswer(ans, new ArrayList<>(), candidates, target, 0); 4. /***修改的地方**/ 5. // 如果是 Input: candidates = [2,5,2,1,2], target = 5, 6. // 输出会出现 [2 2 1] [2 1 2] 这样的情况，所以要去重 7. return removeDuplicate(ans); 8. /*****/ 9. } 10. 11. private void getAnswer(List> ans, ArrayList temp, int[] candidates, int target, int start) { 12. if (target == 0) { 13. ans.add(new ArrayList(temp)); 14. } else if (target < 0) { 15. return; 16. } else { 17. for (int i = start; i < candidates.length; i++) { 18. temp.add(candidates[i]); 19. /**修改的地方**/ 20. //i -> i + 1 ，因为每个数字只能用一次，所以下次遍历的时候不从自己开始 21. getAnswer(ans, temp, candidates, target - candidates[i], i + 1); 22. /********/ 23. temp.remove(temp.size() - 1); 24. } 25. } 26. 27. } 28. 29. private List> removeDuplicate(List> list) { 30. Map ans = new HashMap(); 31. for (int i = 0; i < list.size(); i++) { 32. List l = list.get(i); 33. Collections.sort(l); 34. String key = ""; 35. for (int j = 0; j < l.size() - 1; j++) { 36. key = key + l.get(j) + ","; 37. } 38. key = key + l.get(l.size() - 1); 39. ans.put(key, ""); 40. } 41. List> ans_list = new ArrayList>(); 42. for (String k : ans.keySet()) { 43. String[] l = k.split(","); 44. List temp = new ArrayList(); 45. for (int i = 0; i < l.length; i++) { 46. int c = Integer.parseInt(l[i]); 47. temp.add(c); 48. } 49. ans_list.add(temp); 50. } 51. return ans_list; 52. }

时间复杂度：空间复杂度：看到这里)，想法很棒，为了解决重复的情况，我们可以先把数组先排序，这样就好说了。 1. public List> combinationSum2(int[] candidates, int target) { 2. List> ans = new ArrayList<>(); 3. Arrays.sort(candidates); //排序 4. getAnswer(ans, new ArrayList<>(), candidates, target, 0); 5. return ans; 6. } 7. 8. private void getAnswer(List> ans, ArrayList temp, int[] candidates, int target, int start) { 9. if (target == 0) { 10. ans.add(new ArrayList(temp)); 11. } else if (target < 0) { 12. return; 13. } else { 14. for (int i = start; i < candidates.length; i++) { 15. //跳过重复的数字 16. if(i > start && candidates[i] == candidates[i-1]) continue;
17. temp.add(candidates[i]); 18. /***修改的地方**/ 19. //i -> i + 1 ，因为每个数字只能用一次，所以下次遍历的时候不从自己开始 20. getAnswer(ans, temp, candidates, target - candidates[i], i + 1); 21. /*******/ 22. temp.remove(temp.size() - 1); 23. } 24. } 25. }

解法二动态规划

怎么去更改上题的算法满足本题，暂时没想到，只想到就是再写个函数对答案再过滤一次。先记录给定的 nums 中的每个数字出现的次数，然后判断每个 list 的数字出现的次数是不是满足小于等于给定的 nums 中的每个数字出现的次数，不满足的话就剔除掉。如果大家有直接改之前算法的好办法可以告诉我，谢谢了。此外，要注意一点就是上题中，给定的 nums 没有重复的，而这题中是有重复的。为了使得和之前一样，所以我们在算法中都得加上 1. if (i > 0 && nums[i] == nums[i - 1]) { 2. continue; 3. }

跳过重复的数字，不然是不能 AC 的，至于原因下边分析下。 1. public List> combinationSum2(int[] nums, int target) { 2. List>> ans = new ArrayList<>(); //opt 数组 3. Arrays.sort(nums);// 将数组有序，这样可以提现结束循环 4. for (int sum = 0; sum <= target; sum++) { // 从 0 到 target 求出每一个 opt 5. List> ans_sum = new ArrayList>(); 6. for (int i = 0; i < nums.length; i++) { //遍历 nums 7. /***修改的地方***/ 8. if (i > 0 && nums[i] == nums[i - 1]) { 9. continue; 10. } 11. /********/ 12. if (nums[i] == sum) { 13. List temp = new ArrayList(); 14. temp.add(nums[i]); 15. ans_sum.add(temp); 16. } else if (nums[i] < sum) { 17. List> ans_sub = ans.get(sum - nums[i]); 18. //每一个加上 nums[i] 19. for (int j = 0; j < ans_sub.size(); j++) { 20. List temp = new ArrayList(ans_sub.get(j)); 21. temp.add(nums[i]); 22. ans_sum.add(temp); 23. } 24. } else { 25. break; 26. } 27. } 28. ans.add(sum, ans_sum); 29. } 30. return remove(removeDuplicate(ans.get(target)),nums); 31. } 32. 33. private List> removeDuplicate(List> list) { 34. Map ans = new HashMap(); 35. for (int i = 0; i < list.size(); i++) { 36. List l = list.get(i); 37. Collections.sort(l); 38. String key = ""; 39. //[ 2 3 4 ] 转为 "2,3,4" 40. for (int j = 0; j < l.size() - 1; j++) { 41. key = key + l.get(j) + ","; 42. } 43. key = key + l.get(l.size() - 1); 44. ans.put(key, ""); 45. } 46. //根据逗号还原 List 47. List> ans_list = new ArrayList>(); 48. for (String k : ans.keySet()) { 49. String[] l = k.split(","); 50. List temp = new ArrayList(); 51. for (int i = 0; i < l.length; i++) { 52. int c = Integer.parseInt(l[i]); 53. temp.add(c); 54. } 55. ans_list.add(temp); 56. } 57. return ans_list; 58. } 59. 60. //过滤不满足答案的情况 61. private List> remove(List> list, int[] nums) { 62. HashMap nh = new HashMap(); 63. List> ans = new ArrayList>(list); 64. //记录每个数字出现的次数 65. for (int n : nums) { 66. int s = nh.getOrDefault(n, 0); 67. nh.put(n, s + 1); 68. } 69. for (int i = 0; i < list.size(); i++) { 70. List l = list.get(i); 71. HashMap temp = new HashMap(); 72. //记录每个 list 中数字出现的次数 73. for (int n : l) { 74. int s = temp.getOrDefault(n, 0); 75. temp.put(n, s + 1); 76. } 77. for (int n : l) { 78. //进行比较 79. if (temp.get(n) > nh.get(n)) { 80. ans.remove(l); 81. break; 82. } 83. } 84. } 85. return ans; 86. }

如果不加跳过重复的数字的话，下边的样例不会通过。这是因为我们求 opt 的时候每个列表的数量在以指数级增加，在上一个 opt 的基础上，每一个列表都增加 5 个列表。 opt [ 1 ] = [ [ 1 ]，[ 1 ]，[ 1 ]，[ 1 ]，[ 1 ] ] 数量是 5， opt [ 2 ] = [ [ 1，1 ]， [ 1，1 ]，[ 1，1 ]，[ 1，1 ]，[ 1，1 ]， [ 1，1 ]， [ 1，1 ]，[ 1，1 ]，[ 1，1 ]，[ 1，1 ] [ 1，1 ]， [ 1，1 ]，[ 1，1 ]，[ 1，1 ]，[ 1，1 ]， [ 1，1 ]， [ 1，1 ]，[ 1，1 ]，[ 1，1 ]，[ 1，1 ]， [ 1，1 ]， [ 1，1 ]，[ 1，1 ]，[ 1，1 ]，[ 1，1 ]，， ] 数量是 5 * 5。 opt [ 3 ] 数量是 5 * 5 * 5。到了 opt [ 9 ] 就是 5 的 9 次方，数量是 1953125 内存爆炸了。另一个算法也可以改一下 1. public List> combinationSum2(int[] nums, int target) { 2. List>> ans = new ArrayList<>(); 3. Arrays.sort(nums); 4. if (nums[0] > target) { 5. return new ArrayList>(); 6. } 7. for (int i = 0; i <= target; i++) { 8. List> ans_i = new ArrayList>(); 9. ans.add(i, ans_i); 10. } 11. 12. for (int i = 0; i < nums.length; i++) { 13. /***修改的地方***/ 14. if (i > 0 && nums[i] == nums[i - 1]) { 15. continue; 16. } 17. /********/ 18. for (int sum = nums[i]; sum <= target; sum++) { 19. List> ans_sum = ans.get(sum); 20. List> ans_sub = ans.get(sum - nums[i]); 21. if (sum == nums[i]) { 22. ArrayList temp = new ArrayList(); 23. temp.add(nums[i]); 24. ans_sum.add(temp); 25. 26. } 27. if (ans_sub.size() > 0) { 28. for (int j = 0; j < ans_sub.size(); j++) { 29. ArrayList temp = new ArrayList(ans_sub.get(j)); 30. temp.add(nums[i]); 31. ans_sum.add(temp); 32. } 33. } 34. } 35. } 36. return remove(ans.get(target), nums); 37. 38. } 39. 40. private List> remove(List> list, int[] nums) { 41. HashMap nh = new HashMap(); 42. List> ans = new ArrayList>(list); 43. for (int n : nums) { 44. int s = nh.getOrDefault(n, 0); 45. nh.put(n, s + 1); 46. } 47. for (int i = 0; i < list.size(); i++) { 48. List l = list.get(i); 49. HashMap temp = new HashMap(); 50. for (int n : l) { 51. int s = temp.getOrDefault(n, 0); 52. temp.put(n, s + 1); 53. } 54. for (int n : l) { 55. if (temp.get(n) > nh.get(n)) { 56. ans.remove(l); 57. break; 58. } 59. } 60. } 61. return ans; 62. }