public class Solution

    {

        List<IList<int>> list = new List<IList<int>>();//全部记录

        List<int> records = new List<int>();//一条记录

        bool bk = false;

        private void BackTrack(List<int> candidates, int target, int sum)

        {

            if (sum == target)

            {

                int[] temp = new int[records.Count];

                records.CopyTo(temp);

                bool same = false;

                foreach (var l in list)

                {

                    if (l.Count == temp.Length)

                    {

                        var l1 = l.OrderBy(x => x).ToList();

                        var l2 = temp.OrderBy(x => x).ToList();

                        var samecount = ;

                        for (int x = ; x < l1.Count; x++)

                        {

                            if (l1[x] == l2[x])

                            {

                                samecount++;

                            }

                        }

                        if (samecount == l.Count)

                        {

                            same = true;

                            break;

                        }

                    }

                }

                if (!same)

                {

                    list.Add(temp.ToList());

                }

                bk = true;

                return;

            }

            else if (sum < target)

            {

                bk = true;

                for (int position = ; position < candidates.Count; position++)

                {

                    var cur = candidates[position];

                    sum += cur;

                    records.Add(cur);

                    BackTrack(candidates, target, sum);

                    //回溯

                    records.RemoveAt(records.Count - );

                    sum -= cur;

                    if (bk)

                    {

                        bk = false;

                        break;

                    }

                }

            }

            else

            {

                bk = true;

                return;

            }

        }

        public IList<IList<int>> CombinationSum(int[] candidates, int target)

        {

            var can = candidates.OrderBy(x => x).ToList();

            BackTrack(can, target, );

            return list;

        }

    }

 class Solution:

     def dfs(self,candidates,target,index,path,l):

         if target < 0:

             return

         elif target == 0:

             l.append(path)

             return

         for i in range(index,len(candidates)):

             self.dfs(candidates,target-candidates[i],i,path+[candidates[i]],l)

         return

     def combinationSum(self, candidates: 'List[int]', target: 'int') -> 'List[List[int]]':

         l = list()

         path = []

         candidates.sort()

         self.dfs(candidates,target,0,path,l)

         return l