void back(int* candidates, int candidatesSize, int target,int start,int *path,int *pathSize,int **result,int** returnColumnSizes,int *visited,int* returnSize,int *sum){

    if(*sum == target){

        result[*returnSize] = (int *)malloc(sizeof(int)*(*pathSize));

        memcpy(result[*returnSize],path,sizeof(int)*(*pathSize));

        (*returnColumnSizes)[*returnSize] = *pathSize;

        (*returnSize)++;

        return;

    }

    for(int i=start;i<candidatesSize; i++){

        if((*sum)+candidates[i]>target){break;}

        if(i>0&&candidates[i-1]==candidates[i]&&visited[i-1]==0){

            continue;

        }

        path[*pathSize] = candidates[i];

        (*pathSize)++;

        (*sum) += candidates[i];

        visited[i] = 1;

        back(candidates,candidatesSize,target,i+1,path,pathSize,result,returnColumnSizes,visited,returnSize,sum);

        visited[i] = 0;

        (*sum) -= candidates[i];

        (*pathSize)--;

    }

}

void QuickSort1(int* a, int left, int right)

{

    if (left >= right)

    {

        return;

    }

    int begin = left, end = right;

    //三数取中

    //int midIndex = GetThreeMid(a,begin,end);

    //Swap(&a[begin],&a[midIndex]);

    int pivot = begin;

    int key = a[begin];

    while (begin < end)

    {

        //右边找小的，如果不是小于key,继续

        while (begin < end && a[end] >= key)

        {

            end--;

        }

        //找到比key小的，把它放在坑里，换新坑

        a[pivot] = a[end];

        pivot = end;

        //左边找大的，如果不是大于key,继续

        while (begin < end && a[begin] <= key)

        {

            begin++;

        }

        //找到比key大的，把它放在坑里，换新坑

        a[pivot] = a[begin];

        pivot = begin;

    }

    a[pivot] = key;//bengin 与 end 相遇，相遇的位置一定是一个坑

    QuickSort1(a, left, pivot - 1);

    QuickSort1(a, pivot + 1, right);

}

int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes){

    *returnSize = 0;

    int *path = (int *)malloc(sizeof(int)*candidatesSize);

    int *pathSize = (int *)calloc(1,sizeof(int));

    int **result = (int **)malloc(sizeof(int *)*100001);

    *returnColumnSizes = (int *)malloc(sizeof(int *)*100001);

    int *visited = (int *)calloc(candidatesSize,sizeof(int));

    int *sum = (int *)calloc(1,sizeof(int));

    QuickSort1(candidates,0,candidatesSize-1);

    back(candidates,candidatesSize,target,0,path,pathSize,result,returnColumnSizes,visited,returnSize,sum);

    return result;

}

class Solution {

public:

    vector<vector<int>> result;

    vector<int> path;

    void back(vector<int>& candidates, int target,int start,int sum,vector<bool> &visited){

        if(sum==target){

            result.push_back(path);

            return;

        }

        for(int i=start;i<candidates.size();i++){

            if(sum+candidates[i]>target){break;}

            if(i>0&&candidates[i-1]==candidates[i]&&visited[i-1]==false){continue;}

            path.push_back(candidates[i]);

            sum += candidates[i];

            visited[i] = true;

            back(candidates,target,i+1,sum,visited);

            visited[i] = false;

            sum -= candidates[i];

            path.pop_back();

        }

    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {

        sort(candidates.begin(),candidates.end());

        vector<bool> visited(candidates.size(),false);

        back(candidates,target,0,0,visited);

        return result;

    }

};

class Solution {

    List<List<Integer>> result = new ArrayList<>();

    LinkedList<Integer> path = new LinkedList<>();

    public void back(int[] candidates, int target,int start,int sum,boolean[] visited){

        if(sum==target){

            result.add(new ArrayList(path));

            return;

        }

        for(int i=start;i<candidates.length;i++){

            if(sum+candidates[i]>target){break;}

            if(i>0&&candidates[i-1]==candidates[i]&&visited[i-1]==false){continue;}

            path.addLast(candidates[i]);

            visited[i] = true;

            sum += candidates[i];

            back(candidates,target,i+1,sum,visited);

            sum -= candidates[i];

            visited[i] = false;

            path.removeLast();

        }

    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        Arrays.sort(candidates);

        boolean[] visited = new boolean[candidates.length];

        Arrays.fill(visited,false);

        back(candidates,target,0,0,visited);

        return result;

    }

}