leetCode/leetCode_216.java at master · mehtabgill/leetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// class Solution {
//     List<List<Integer>> result = new ArrayList<>();

//     public List<List<Integer>> combinationSum3(int k, int n) {


//         return backtrack(1, k, n);
//     }

//      List<List<Integer>> backtrack(int start, int k, int target){

//         List<List<Integer>> ll = new ArrayList<>();

//         if( k == 2 ){
//             int left= start;
//             int right = 9;
//             while(left < right){
//                 int sum = left + right;
//                 if(sum == target){
//                     List<Integer> temp = new ArrayList<>();
//                     temp.add(left);
//                     temp.add(right);
//                     ll.add(temp);
//                     left++;
//                     right--;
//                 }else if(sum > target) right--;
//                 else left++;
//             }
//             return ll;
//         }

//         for(int i=start; i <= 7; i++){
//             if(i > target) continue;
//             List<List<Integer>> temp = backtrack(i+1, k-1, target-i);
//             for(List<Integer> tt: temp){
//                 tt.add(0, i);
//             }
//             ll.addAll(temp);
//         }
//         return ll;
//     }
// }


class Solution {
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {


        backtrack(1, k, n, new ArrayList<>());
        return result;
    }

     void backtrack(int start, int k, int target, List<Integer>list){

        if(list.size() == k && target == 0){
            List<Integer> ll= new ArrayList<>(list);
            result.add(ll);
            return ;
        }

        for(int i=start; i <= 9; i++){
            if(i > target) continue;
            list.add(i);
            backtrack(i+1, k, target-i, list);
            list.remove(list.size()-1);
        }
    }
}