# Please help me apply this subtle iterative method(thx @peike) of combination sum into combi sum II

• ``````//iterative
Arrays.sort(num);
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
Stack<Integer> combi = new Stack<>(), idx = new Stack<>();
int i = 0, sum = 0, len = num.length;
while(i < len){
if(sum + num[i] < target){
combi.push(num[i]);
sum += num[i];
idx.push(i);
}else{
if(sum + num[i] == target){
combi.push(num[i]);
combi.pop();
}
//the size of combi and idx should be the same
if(!idx.isEmpty()){
sum -= combi.pop();
i = idx.pop();
while(i == len - 1 && !idx.isEmpty()){
i = idx.pop();
sum -= combi.pop();
}
}
i++;
}
}
return res;``````

• I also tried to adapt @peike 's combination sum into combi sum II. I use hashset to avoid duplicated solutions.
I'm new to coding. I would really appreciate it if any of you can help me improve my code. Thanks.

`````` public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
if(candidates == null || candidates.length==0)
return list;
Arrays.sort(candidates);
//index of candidates
int i = 0, size = candidates.length, sum = 0;

//stack for numbers so they can be added to list
Stack<Integer> item = new Stack<>();
//stack to track index
Stack<Integer> indices = new Stack<>();
//hashset guarantees unique result since duplicate element is alloweded
HashSet<ArrayList<Integer>> pool = new HashSet<ArrayList<Integer>>();

while(i<size) {
if (sum + candidates[i] >= target) {
if (sum + candidates[i] == target) {
item.push(candidates[i]);
item.pop();
}
//if it is over sum then we need to use new number by increase index
if(!indices.isEmpty()) {
sum -= item.pop();
i = indices.pop();
}
i++;
} else {
//if sum is still less than target after adding last element,
//pop previous element and move on to next available element
if (i == size-1) {
if (item.isEmpty()) break;
else {
sum -= item.pop();
i = indices.pop()+1;
}
}
//this means no element available, it will go to above lines keeps poping stack
if (i == size-1)
continue;
item.push(candidates[i]);
sum += candidates[i];
indices.push(i);
i++;
}
}
return new ArrayList<List<Integer>>(pool);
}``````

• The code is as follows:

• ``````public class Solution {
public List<List<Integer>> combinationSum2(int[] num, int target) {
if(num == null || num.length == 0) return new ArrayList<List<Integer>>();
Arrays.sort(num);
//items store the elements in the num and indices store index of the corresponding element
Stack<Integer> items = new Stack<>();
Stack<Integer> indices = new Stack<>();
ArrayList<List<Integer>> res = new ArrayList<>();
int idx = 0, sum = 0;
while(idx < num.length){
if(sum + num[idx] >= target){
if(sum + num[idx] == target){
items.push(num[idx]);
items.pop();
}
if(indices.isEmpty()) break;
sum -= items.pop();
idx = indices.pop() + 1;
//handle the same value elements
while(idx > num.length - 1 || num[idx] == num[idx - 1]){
if(idx > num.length - 1){
if(indices.isEmpty()) break;
idx = indices.pop() + 1;
sum -= items.pop();
}else if(num[idx] == num[idx - 1]){
idx++;
}
}
}else{
if(idx == num.length - 1){
if(indices.isEmpty()) break;
idx = indices.pop() + 1;
sum -= items.pop();
while(idx > num.length - 1 || num[idx] == num[idx - 1]){
if(idx > num.length - 1){
if(indices.isEmpty()) break;
idx = indices.pop() + 1;
sum -= items.pop();
}else if(num[idx] == num[idx - 1]){
idx++;
}
}
}else{
items.push(num[idx]);
sum += num[idx];
indices.push(idx++);
}
}
}
return res;
}
}``````

• And I've rewritten your new code :P (C++)

``````class Solution {
public:
vector<vector<int>> combinationSum2(vector<int> &num, int target) {
vector<int> numbers = num;  // Why not? This algorithm cost only 16ms for all tests.
sort(numbers.begin(), numbers.end());
vector<vector<int>> result;
vector<int> subset;
vector<int> stack;
int i = 0;
while (i < numbers.size()) {
if (target - numbers[i] == 0) {
result.push_back(subset);
result.back().push_back(numbers[i]);
}
if (target - numbers[i] <= 0 ||
(target - numbers[i] > 0 && i == numbers.size() - 1) ||
(target > numbers.back() * (numbers.size() - i))) {
if (stack.empty()) return result;
target += subset.back();
subset.pop_back();
i = stack.back() + 1;
stack.pop_back();
// avoid duplicates
while (i >= numbers.size() || (i > 0 && numbers[i-1] == numbers[i])) {
if (i >= numbers.size()) {
if (stack.empty()) return result;
target += subset.back();
subset.pop_back();
i = stack.back() + 1;
stack.pop_back();
} else {
i++;
}
}
} else {
subset.push_back(numbers[i]);
target -= numbers[i];
stack.push_back(i);
i++;
}
}
return result;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.