Leetcode

Leetcode

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

思路

题意是让你从给定的数组中找到两个元素的和为指定值的两个索引，利用HashMap作为存储，键为目标值减去当前元素值，索引为值，比如i = 0时，此时首先要判断nums[0] = 2是否在map中，如果不存在，那么插入键值对key = 9 - 2 = 7, value = 0，之后当i = 1时，此时判断nums[1] = 7已存在于map中，那么取出该value = 0作为第一个返回值，当前i作为第二个返回值。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int len = nums.length;　　　　//数组长度
        HashMap<Integer,Integer> map = new HashMap<>();  //新建HashMap
        for(int i=0 ; i<len; i++){
            if(map.containsKey(nums[i])){　　　　//遍历数组中的元素是否在HashMap中
                return new int[]{map.get(nums[i]),i};
            }
            map.put(target - nums[i],i);
        }
        return null;
    }
}

26. Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length.Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

思路

题意是让你从一个有序的数组中移除重复的元素，并返回之后数组的长度。我的思路是：首先判断如果数组长度等于0的话直接返回原长度即可，否则的话遍历一遍数组，用一个index变量指向尾部，如果后面的元素和前面的元素不同，就让index变量加1，最后返回index。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int len = nums.size();    //输出数组长度
        if(len==0) return len;
        int index = 0;　　　　　　 //index
        for(int i=1; i<len; i++){　　　　//遍历数组
            if(nums[index]!=nums[i]){　　
                nums[++index] = nums[i];  //判断后面的元素是否和前面的相同
            }
        }
        return index+1;
        
    }
};

27. Remove Element

Given an array and a value, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:

Given nums = [3,2,2,3], val = 3,

Your function should return length=2, with the first two elements of nums being 2.

思路

题意是移除数组中值等于val的元素，并返回之后数组的长度，并且题目中指定空间复杂度为O(1)，我的思路是用index标记尾部，遍历该数组时当索引元素不等于val时，index加一，尾部指向当前元素，最后返回index即可。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int index = 0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]!= val){
                nums[index++]=nums[i];
            }
        }
        return index;
    }
    
};

33. Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

思路

题意是让你从一个旋转过后的递增序列中寻找给定值，找到返回索引，找不到返回-1，我们在下面这组数据中寻找规律。

1 2 4 5 6 7 0
2 4 5 6 7 0 1
4 5 6 7 0 1 2
5 6 7 0 1 2 4
6 7 0 1 2 4 5
7 0 1 2 4 5 6

由于是旋转一次，所以肯定有一半及以上的序列仍然是具有递增性质的，我们观察到如果中间的数比左面的数大的话，那么左半部分序列是递增的，否则右半部分就是递增的，那么我们就可以确定给定值是否在递增序列中，从而决定取舍哪半边。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0, right = nums.size();
        while(left != right){
            int mid = (left+right)/2;
            if(nums[mid] == target) return mid;
            if(nums[left]<=nums[mid]){
                if(nums[left]<=target&&target<=nums[mid]){
                    right = mid;
                }
                else
                    left = mid+1;
            }else{
                if(nums[mid]<target && target<=nums[right-1]){
                    left = mid+1;
                    
                }
                else
                    right = mid;
            }
        }
        return -1;  
    }
};

15. 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路

题意是让你从数组中找出所有三个和为0的元素构成的非重复序列，这样的话我们可以把数组先做下排序，然后遍历这个排序数组，用两个指针分别指向当前元素的下一个和数组尾部，判断三者和与0的大小来移动两个指针，其中细节操作就是注意去重。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        int i=0;
        while(i<nums.length-2){
            if(nums[i]>0) break;
            int left = i+1, right = nums.length-1;
            while(left<right){
                int sum = nums[i]+nums[left]+nums[right];
                if(sum == 0){
                    list.add(Arrays.asList(nums[i],nums[left++],nums[right--]));
                    while(left<right && nums[left] == nums[left-1]) ++left;
                    while(left<right && nums[right] == nums[right+1]) --right;
                    
                }else if(sum < 0 ) ++left;
                else --right;
            }
            while(nums[i] == nums[++i] && i<nums.length -2);
            
        }
        return list;
    }
}

16. 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

思路

题意是让我们求最接近给定值的三数之和，是在之前那道3Sum三数之和的基础上又增加了些许难度，那么这道题让我们返回这个最接近于给定值的值，即我们要保证当前三数和跟给定值之间的差的绝对值最小，所以我们需要定义一个变量Ａ用来记录差的绝对值，然后我们还是要先将数组排个序，然后开始遍历数组，思路跟那道三数之和很相似，都是先确定一个数，然后用两个指针left和right来滑动寻找另外两个数，每确定两个数，我们求出此三数之和，然后算和给定值的差的绝对值存在newＡ中，然后和Ａ比较并更新Ａ和结果closest即可。

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int closest = nums[0]+nums[1]+nums[2];
        int A = abs(closest-target);
        sort(nums.begin(),nums.end());
        for(int i=0; i<nums.size()-2; i++){
            int left = i+1, right = nums.size()-1;
            while(left<right){
                int sum = nums[i]+nums[left]+nums[right];
                int newA = abs(sum-target);
                if(A>newA){
                    A = newA;
                    closest = sum;
                }
                if(sum<target) ++left;
                else --right;
            }
        }
        return closest;
    }
};

53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

思路

题意是求数组中子数组的最大和，利用动态规划的方法去求解。当部分序列和大于0的话就一直加下一个元素，并和当前最大值进行比较，如果出现部分序列小于０，那就需要从当前元素算起。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size(), init = nums[0], max = init;
        
        for(int i=1; i<len; i++){
            init = nums[i]+(init>0 ? init:0);
            if(init>max) max = init;
        }
        return max;
         
    }
};

38. Count and Say

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"

Example 2:

Input: 4
Output: "1211"

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

思想

题意是用一个新链表来合并两个已排序的链表，那我们只需要从头开始比较已排序的两个链表，新链表指针每次指向值小的节点，依次比较下去，最后，当其中一个链表到达了末尾，我们只需要把新链表指针指向另一个没有到末尾的链表此时的指针即可。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode tmp = head;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                tmp.next = l1;
                l1 = l1.next;
            }else{
                tmp.next = l2;
                l2 = l2.next;
            }
            tmp = tmp.next;
        }
        tmp.next = l1 !=null ? l1:l2;
        return head.next;
    }
}

11. Container With Most Water

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

思路

木桶的容积取决于短板的高度。首先计算最左边（left）和最右边（right）组成的木桶的面积，并把它设置为maxArea。在left<right的情况下，首先判断height[left]和height[right]值的大小，若height[left]<height[right]，则height取值向右边移动，同时计算每移动一步后新的Area的面积并与maxArea做比较，得出新的最大面积；反之，则height取值向左边移动，重复上一步操作。最终得到最大的区域积。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right =height.size()-1; 
        int maxArea = (right-left)*min(height[left],height[right]);
        while(left<right){
            if(height[left]<height[right]){
                left++;
                int Area1 = (right-left)*min(height[left],height[right]);
                if(Area1>maxArea){
                    maxArea = Area1;
                }
            }
            else{
                right--;
                int Area2 = (right-left)*min(height[left],height[right]);
                if(Area2>maxArea){
                    maxArea = Area2;
                }
            }
        }
        return maxArea;
    }
};

14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

思路

题意是编写一个函数来查找字符串数组中最长的公共前缀字符串。利用纵向扫描，对每一个位置比较所以字符串，直到遇到一个不匹配。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.empty()) return "";
        for(int idx=0; idx<strs[0].size(); idx++){  //纵向扫描数组
            for(int i=1; i<strs.size(); i++){
                if(strs[i][idx] != strs[0][idx]) return strs[0].substr(0,idx);
            }
        }
        return strs[0];
    }
};

//strs = ['make fun','make love','main idea'];
//strs[0] = 'make fun' thus idx (0~8);
//strs.size() = 3; 
//strs[i][idx],strs[0][idx]中，保持idx不变，比较纵列是否相同。
//strs[0].substr(0,idx)　substr(截取开始位置,截取长度)。

9. Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

思路

题意是判断一个有符号整型数是否是回文，也就是逆序过来的整数和原整数相同，首先负数肯定不是，接下来我们直接算出他的回文数，然后和给定值比较即可。

class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0) return false;
        int s = x, reverse = 0;
        while(s>0){
            reverse = reverse*10+s%10;
            s/=10;
        }
        return x == reverse;
    }
};
//reverse = 1      reverse = 12      reverse=123      reverse=1234
//reverse = 12344  reverse = 123443  reverse=1234432  reverse=12344321

35. Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

Example 3:

Input: [1,3,5,6], 7
Output: 4

Example 1:

Input: [1,3,5,6], 0
Output: 0

思路

题意是给定一个有序数组和一个目标值，如果找到目标，则返回索引。如果没有，则返回按顺序插入的索引。解题思路：首先遍历数组，若当前数字大于或等于目标值，则返回当前坐标，如果遍历结束了，说明目标值比数组中任何一个数都要大，则返回数组长度n即可。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        for(int i=0; i<nums.size(); i++){
            if(nums[i]>=target) return i;
        }
        return nums.size();
    }
};

48. Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Given input matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

Example 2:

Given input matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

rotate the input matrix in-place such that it becomes:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

思路

题意是给定一个n*n个2维矩阵来表示一个图。在原矩阵上旋转图形90°。主要思路是，首先沿着矩阵副对角线翻转一次，然后沿着水平线翻转一次。

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int i, j, temp;
        int n = matrix.size();
        # 沿着矩阵副对角线翻转
        for(int i=0; i<n; ++i){
            for(int j=0; j<n-i; ++j){
                temp = matrix[i][j];
                matrix[i][j] = matrix[n-j-1][n-i-1];
                matrix[n-j-1][n-i-1] = temp;
            }
        }
        # 沿着水平线翻转
        for(int i=0; i<n/2; ++i){
            for(int j=0; j<n; ++j){
                temp = matrix[i][j];
                matrix[i][j] = matrix[n-i-1][j];
                matrix[n-i-1][j] = temp;
            }
        }
    }
};

34. Search for a Range

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

思路

题意是给定按升序排序的整数数组，找到给定目标值的开始和结束位置。其中算法的运行时复杂度必须按照O（log n）的顺序。如果在数组中找不到目标，则返回[-1，-1]。首先，建立二元结果数组Ａ，左边left,右边right。二分法求左边界：当中点小于target，left移向中点，否则right移向中点；先判断左边，再判断右边是否等于target，如果是，赋值给Ａ[0]。二分法求右边界：当中点大于target，right移向中点，否则left移向中点；先判断右边，再判断左边是否等于target，如果是，赋值给Ａ[1]。返回Ａ。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        int[] A = {-1,-1};
        int left=0,right = n-1;
        while(nums[left]<nums[right]){
            int mid = left + (right-left)/2;
            if(nums[mid]<target) left = mid+1;
            else if(nums[mid]>target) right = mid-1;
            else{
                if(nums[left]<target) left++;
                if(nums[right]>target) right--;
            }
        }
        if(nums[left] == target){
            A[0] = left;
            A[1] = right;
        }
        return A;
    }
}

66. Plus One

Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.

You may assume the integer do not contain any leading zero, except the number 0 itself.

The digits are stored such that the most significant digit is at the head of the list.

思路

题意是给定一个数组表示非负整数，其高位在数组的前面，对这个整数加1。使用大数加法，遍历数组的每一位，同时处理进位，如果最后还有进位，则在数组最前面插入１即可。

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int c = 1;
        int n = digits.size();
      　＃ 遍历数组的每一位
        for(int i = n-1; i>=0; i--){
            int a = digits[i]+c;
            digits[i] = a % 10;
          　// 做进位处理
            c = a/10; 
            // 用于判断最后是否还有进位，值为０或１．
        }
        if(c == 1){
            digits.insert(digits.begin(), 1);
            // 在数组最前面插入１．
        }
        return digits;
    }
};

121. Best Time to Buy and Sell Stock

Say you have an array for which the $i^{th}$ element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

思路

题意是假设有一个数组，数组中的元素是第i天给定股票的价格，如果最多只能完成最多一笔交易（买入或者卖出一股股票），设计一个算法来找到最大的利润值。首先初始化利润值为０，假定当前的最小值cur_min为数组中的第一个数值，遍历当前数组，取初始化利润值与prices[i]-cur_min中较大值作为新的profit，取cur_min和prices[i]中较小的值作为新的cur_min，迭代最终得到最大的profit。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n<2) return 0;
        int profit = 0; // 初始化利润值.
        int cur_min = prices[0];  // 当前的最小股票值
        for(int i=0; i<n; i++){
            profit = max(profit, prices[i]-cur_min);
            cur_min = min(cur_min, prices[i]);
        }
        return profit;
    }
};

122. Best Time to Buy and Sell Stock II

Say you have an array for which the $i^{th}$ element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

思路

题意是设计一个算法来找到最大的利润，可以根据需要完成尽可能多的交易（即多次买入和卖出一次股票）。但是不可以同时进行多笔交易（即您必须在再次购买之前出售股票）。因为买一次接着卖一次，所以只要计算买卖一次的利润值，对利润值大于０的进行求和。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int sum = 0;
        for(int i = 1; i<n; i++){
            int profit = prices[i]-prices[i-1];
            if(profit>0) sum += profit;
        }
        return sum;
    }
};

118. Pascal’s Triangle

Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

思路

题意是生成帕斯卡三角形，我们可以发现，从第三行开始，该行中的值等于上一行的左上角和右上角之和，利用这个规律进行求解。

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> result;
        //在vector<vector<int>>中，因为vector是一个容器，最外层的vector容器中放着更小的             vector，而里层的vector里面放的是int型的数字。所以我们首先要对里层的vector容器赋           值，然后再把里层的vector作为元素插入到外层的vector中。
        if(numRows == 0) return result; 
        result.push_back(vector<int>(1,1));
        for(int i=2; i<=numRows; i++){
            vector<int> current(i,1);  //本行
            vector<int> &pre = result[i-2]; //　上一行
            
            for(int j=1; j<i-1; j++){
                current[j] = pre[j-1]+pre[j];　//左上角和右上角之和
            }
            result.push_back(current);　//在vector类中作用为在vector尾部加入一个数据
            
        }
        return result;
    }
};

119. Pascal’s Triangle II

Given an index k, return the $k^th$ row of the Pascal’s triangle.

For example, given k = 3, Return [1,3,3,1].

思路

题意是生成帕斯卡三角形中的某一列。

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> array;
        for(int i=0; i<=rowIndex; i++){
            for(int j=i-1; j>0; j--){
                array[j] = array[j-1]+array[j];
            }
            array.push_back(1);
        }
        return array;
    }
};

39. Combination Sum

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

[
  [7],
  [2, 2, 3]
]

思路

题意：给定一个正数集合和一个目标数，求出所有的子集合，使子集的和为target，要求子集合递增排列，且不包含重复的子集合，子集合中的数字可以重复。我们需要写一个递归函数，在这个函数中需要添加三个变量，result记录最终的结果，path记录中间的一个解，start记录当前递归到的下标。调用递归函数时，target要减去当前数组的数，为了减小计算量，进行相应的剪枝处理，即大于target,就减去。数组中的那个值。

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> result; //final result
        vector<int> path;   // path result
        combsum(candidates, path, result, target, 0);
        return result;
        
    }
    
private:
    void combsum(vector<int>& candidates, vector<int>& path, vector<vector<int>>& result, int target, int start){
        if(target == 0){     // find the suitable solution
            result.push_back(path);
            return;
        } 
        for(int i=start; i<candidates.size(); i++){
            if(target<candidates[i]) return ;   //pruning
            
            path.push_back(candidates[i]);
            combsum(candidates, path, result, target-candidates[i],i);
            path.pop_back();    
        }
    }
};

40. Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

思路

题意：给定一个正数集合和一个目标数，求出所有的子集合，使子集的和为target，要求子集合递增排列，且不包含重复的子集合，子集合中的数字也不可以重复。与上一个题目差不多，需要加一个判断，如果上一轮循环已经使用candidates[i]，本次循环就不能再选candidates[i]，确保candidates[i]最多循环一次。

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> result;
        vector<int> path;
        combsum(candidates, path, result, target, 0);
        return result;
        
    }
private:
    void combsum(vector<int>& candidates, vector<int>& path, vector<vector<int>>& result, int target, int start){
        if(target == 0){
            result.push_back(path);
            return ;
        }
        
        int previous = -1;
        for(int i=start; i<candidates.size(); i++){
            // if previous loop has used candidates[i], 
            // in this loop candidates[i] can not be used
            if(previous == candidates[i]) continue;    
            if(target<candidates[i]) return ;  //pruning
            
            previous = candidates[i];
            
            path.push_back(candidates[i]);
            combsum(candidates, path, result, target-candidates[i], i+1);
            path.pop_back();
            
        }
    }
};