Programming Puzzles
  • Introduction
  • CTCI
    • Arrays and Strings
      • Is Unique
      • Check Permutation
      • URLify
      • Palindrome Permutation
      • One Away
      • String Compression
      • Rotate Matrix
      • Zero Matrix
      • String Rotation
    • Linked Lists
      • Remove Dups
      • Return Kth to Last
      • Delete Middle Node
      • Sum Lists
      • Palindrome
      • Intersection
    • Trees
      • Route Between Nodes
      • Minimal Tree
      • Check Balanced
      • Build Order
      • First Common Ancestor
      • BST Sequences
      • Check Subtree
      • Random Node
    • Stacks and Queues
      • Three in One
      • Stack Min
      • Stack of Plates
      • Queue via Stacks
      • Sort Stack
    • Sorting and Searching
      • Sorted Merge
      • Group Anagrams
      • Search in Rotated Array
      • Sorted Search, No Size
      • Sparse Search
      • Sort Big File
      • Missing Int
      • Find Duplicates
      • Sorted Matrix Search
    • Bit Manipulation
      • Insertion
    • Math and Puzzles
      • Two Ropes
      • Nine Balls
      • The Heavy Pill
      • Basketball
      • Dominos
    • Recursion and Dynamic Programming
      • Triple Step
      • Robot in a Grid
      • Magic Index
      • Power Set
      • Recursive Multiply
      • Towers of Hanoi
      • Permutations without Dups
      • Parens
      • Paint Fill
      • Coins
    • Object Oriented Design
      • Circular Array
    • Moderate
      • Number Swapper
      • Word Frequencies
      • Intersection
      • Tic Tac Win
      • Factorial Zeros
      • Smallest Difference
      • Number Max
      • Operations
      • Living People
      • Diving Board
      • Bisect Squares
      • Best Line
      • Sub Sort
      • Contiguous Sequence
      • Pattern Matching
      • Pond sizes
      • T9
      • Sum Swap
      • Pairs with Sum
    • Hard
      • Add Without Plus
      • Shuffle
      • Random Set
      • Count of 25
      • Baby Names
      • Majority Element
      • Word Distance
      • The Masseuse
      • Word Transformer
      • Sparse Similarity
  • EoPI
    • Arrays and Strings
  • LeetCode
    • 3 Longest Substring Without Repeating Characters
    • 4 Median of Two Sorted Arrays
    • 5 Longest Palindromic Substring
    • 6 ZigZag Conversion
    • 7 Reverse Integer
    • 8 String to Integer (atoi)
    • 9 Palindrome Number
    • 11 Container With Most Water
    • 14 Longest Common Prefix
    • 15 3Sum
    • 16 3Sum Closest
    • 17 Letter Combinations of a Phone Number
    • 19 Remove Nth Node From End of List
    • 20 Valid Parentheses
    • 21 Merge Two Sorted Lists
    • 22 Generate Parentheses
    • 23 Merge k Sorted Lists
    • 24 Swap Nodes in Pairs
    • 26 Remove Duplicates from Sorted Array
    • 27 Remove Element
    • 28 Implement strStr()
    • 29 Divide Two Integers
    • 30 Substring with Concatenation of All Words
    • 32 Longest Valid Parentheses
    • 33 Search in Rotated Sorted Array
    • 34 Search for a Range
    • 35 Search Insert Position
    • 36 Valid Sudoku
    • 37 Sudoku Solver
    • 38 Count and Say
    • 40 Combination Sum II
    • 41 First Missing Positive
    • 42 Trapping Rain Water
    • 43 Multiply Strings
    • 44 Wildcard Matching
    • 45 Jump Game II
    • 46 Permutations
    • 48 Rotate Image
    • 49 Group Anagrams
    • 53 Maximum Subarray
    • 54 Spiral Matrix
    • 59 Spiral Matrix II
    • 62 Unique Paths
    • 64 Minimum Path Sum
    • 66 Plus One
    • 67 Add Binary
    • 68 Text Justification
    • 69 Sqrt(x)
    • 70 Climbing Stairs
    • 71 Simplify Path
    • 73 Set Matrix Zeroes
    • 74 Search a 2D Matrix
    • 75 Sort Colors
    • 80 Remove Duplicates from Sorted Array II
    • 83 Remove Duplicates from Sorted List
    • 90 Subsets II
    • 91 Decode Ways
    • 99 Recover Binary Search Tree
    • 100 Same Tree
    • 103 Binary Tree Zigzag Level Order Traversal
    • 104 Maximum Depth of Binary Tree
    • 105 Construct Binary Tree from Preorder and Inorder Traversal
    • 112 Path Sum
    • 114 Flatten Binary Tree to Linked List
    • 119 Pascal's Triangle II
    • 120 Triangle
    • 128 Longest Consecutive Sequence
    • 129 Sum Root to Leaf Numbers
    • 133 Clone Graph
    • 136 Single Number
    • 137 Single Number II
    • 138 Copy List with Random Pointer
    • 144 Binary Tree Preorder Traversal
    • 146 LRU Cache
    • 148 Sort List
    • 150 Evaluate Reverse Polish Notation
    • 155 Min Stack
    • 157 Read N Characters Given Read4
    • 161 One Edit Distance
    • 162 Find Peak Element
    • 163 Missing Ranges
    • 167 Two Sum II - Input array is sorted
    • 168 Excel Sheet Column Title
    • 170 Two Sum III - Data structure design
    • 173 Binary Search Tree Iterator
    • 186 Reverse Words in a String II
    • 189 Rotate Array
    • 199 Binary Tree Right Side View
    • 200 Number of Islands
    • 202 Happy Number
    • 207 Course Schedule
    • 210 Course Schedule II
    • 214 Shortest Palindrome
    • 216 Combination Sum III
    • 217 Contains Duplicate
    • 221 Maximal Square
    • 226 Invert Binary Tree
    • 227 Basic Calculator II
    • 228 Summary Ranges
    • 229 Majority Element II
    • 230 Kth Smallest Element in a BST
    • 234 Palindrome Linked List
    • 236 Lowest Common Ancestor of a Binary Tree
    • 237 Delete Node in a Linked List
    • 239 Sliding Window Maximum
    • 240 Search a 2D Matrix II
    • 242 Valid Anagram
    • 243 Shortest Word Distance
    • 245 Shortest Word Distance III
    • 246 Strobogrammatic Number
    • 247 Strobogrammatic Number II
    • 253 Meeting Rooms II
    • 255 Verify Preorder Sequence in Binary Search Tree
    • 256 Paint House
    • 258 Add Digits
    • 260 Single Number III
    • 261 Graph Valid Tree
    • 263 Ugly Number
    • 264 Ugly Number II
    • 266 Palindromic Permutation
    • 270 Closest Binary Search Tree Value
    • 271 Encode and Decode Strings
    • 277 Find the Celebrity
    • 279 Perfect Squares
    • 280 Wiggle Sort
    • 281 Zigzag Iterator
    • 283 Move Zeroes
    • 284 Peeking Iterator
    • 285 Inorder Successor in BST
    • 286 Walls and Gates
    • 288 Unique Word Abbreviation
    • 290 Word Pattern
    • 292 Nim Game
    • 293 Flip Game
    • 296 Best Meeting Point
    • 297 Serialize and Deserialize Binary Tree
    • 298 Binary Tree Longest Consecutive Sequence
    • 301 Remove Invalid Parentheses
    • 304 Range Sum Query 2D - Immutable
    • 310 Minimum Height Trees
    • 311 Sparse Matrix Multiplication
    • 312 Burst Balloons
    • 313 Super Ugly Number
    • 315 Count of Smaller Numbers After Self
    • 316 Remove Duplicate Letters
    • 317 Shortest Distance from All Buildings
    • 319 Bulb Switcher
    • 322 Coin Change
    • 323 Number of Connected Components in an Undirected Graph
    • 326 Power of Three
    • 330 Patching Arrays
    • 333 Largest BST Subtree
    • 334 Increasing Triplet Subsequence
    • 335 Self Crossing
    • 338 Counting Bits
    • 340 Longest Substring with At Most K Distinct Characters
    • 344 Reverse String
    • 345 Reverse Vowels of a String
    • 346 Moving Average from Data Stream
    • 347 Top K Frequent Elements
    • 349 Intersection of Two Arrays
    • 356 Line Reflection
    • 357 Count Numbers with Unique Digits
    • 359 Logger Rate Limiter
    • 361 Bomb Enemy
    • 362 Design Hit Counter
    • 366 Find Leaves of Binary Tree
    • 367 Valid Perfect Square
    • 369 Plus One Linked List
    • 379 Design Phone Directory
    • 387 First Unique Character in a String
    • 389 Find the Difference
    • 394 Decode String
    • 395 Longest Substring with At Least K Repeating Characters
    • 396 Rotate Function
    • 399 Evaluate Division
    • 403 Frog Jump
    • 404 Sum of Left Leaves
    • 406 Queue Reconstruction by Height
    • 409 Longest Palindrome
    • 417 Pacific Atlantic Water Flow
    • 418 Sentence Screen Fitting
    • 422 Valid Word Square
    • 425 Word Squares
    • 434 Number of Segments in a String
    • 435 Non-overlapping Intervals
    • 438 Find All Anagrams in a String
    • 441 Arranging Coins
    • 445 Add Two Numbers II
    • 453 Minimum Moves to Equal Array Elements
    • 476 Number Complement
    • 482 License Key Formatting
    • 494 Target Sum
    • 496 Next Greater Element I
    • 500 Keyboard Row
    • 503 Next Greater Element II
    • 505 The Maze II
    • 506 Relative Ranks
    • 507 Perfect Number
    • 513 Find Bottom Left Tree Value
    • 514 Freedom Trail
    • 517 Super Washing Machines
    • 523 Continuous Subarray Sum
    • 530 Minimum Absolute Difference in BST
    • 531 Lonely Pixel I
    • 534 Design TinyURL
    • 545 Boundary of Binary Tree
    • 551 Student Attendance Record I
    • 554 Brick Wall
    • 563 Binary Tree Tilt
    • 567 Permutation in String
    • 572 Subtree of Another Tree
    • 604 Design Compressed String Iterator
    • 605 Can Place Flowers
    • 606 Construct String from Binary Tree
    • 624 Maximum Distance in Arrays
    • 630 Course Schedule III
    • 652 Find Duplicate Subtrees
    • 654 Maximum Binary Tree
    • 657 Judge Route Circle
    • 665 Non-decreasing Array
    • 669 Trim a Binary Search Tree
    • 672 Bulb Switcher II
    • 677 Map Sum Pairs
    • 681 Next Closest Time
    • 684 Redundant Connection
    • 686 Repeated String Match
    • 690 Employee Importance
    • 692 Top K Frequent Words
    • 212 Word Search II
    • 360 Sort Transformed Array
    • 616 Add Bold Tag in String
    • 318 Maximum Product of Word Lengths
    • 341 Flatten Nested List Iterator
    • 272 Closest Binary Search Tree Value II
    • 56 Merge Intervals
    • 215 Kth Largest Element in an Array
    • 98 Validate Binary Search Tree
    • 351 Android Unlock Patterns
    • 289 Game of Life
    • 575 Distribute Candies
    • 47 Permutations II
    • 267 Palindrome Permutation II
    • 308 Range Sum Query 2D - Mutable
    • 348 Design Tic-Tac-Toe
    • 68 Text Justification
    • 125 Valid Palindrome
    • 139 Word Break
    • 661 Image Smoother
    • 485 Max Consecutive Ones
    • 208 Implement Trie (Prefix Tree)
    • 140 Word Break II
    • 487 Max Consecutive Ones II
    • 61 Rotate List
    • 498 Diagonal Traverse
    • 231 Power of Two
    • 520 Detect Capital
    • 473 Matchsticks to Square
    • 127 Word Ladder
    • 251 Flatten 2D Vector
    • 244 Shortest Word Distance II
    • 245 Shortest Word Distance III
    • 423 Reconstruct Original Digits from English
    • 676 Implement Magic Dictionary
    • 332 Reconstruct Itinerary
    • 718 Maximum Length of Repeated Subarray
    • 172 Factorial Trailing Zeroes
    • 713 Subarray Product Less Than K
    • 36 Valid Sudoku
    • 752 Open the Lock
    • 65 Valid Number
    • 760 Find Anagram Mappings
    • 582 Kill Process
    • 594 Longest Harmonious Subsequence
    • 581 Shortest Unsorted Continuous Subarray
    • 599 Minimum Index Sum of Two Lists
    • 635 Design Log Storage System
    • 642 Design Search Autocomplete System
    • 379 Design Phone Directory
    • 295 Find Median from Data Stream
    • 232 Implement Queue using Stacks
    • 383 Ransom Note
    • 278 First Bad Version
    • 206 Reverse Linked List
    • 787 Cheapest Flights Within K Stops
    • 818 Race Car
    • Categorical
    • Array and Strings
      • Max Avg Number
      • Circular Array Cycle
      • Molecular Weight
      • Itoa
      • Average GPA
      • In Fibonacci Sequence
      • Shortest Rotated Distance
      • Sub-array Factor
      • Matrix Convolution
      • Add One to Array
      • Sum Two Arrays
      • Array Transformation
      • Unique Sub Arrays
      • Reverse and Simplify String
      • Reverse String
      • Information Masking
      • Minimum Array Reduction
      • Add Numbers in Unclean Data
      • Array Operations
      • Equilibrium Index
      • Visit All Places in Minimum Time
    • Linked List
      • Double Linked List Connected Components
    • Trees and Graphs
      • Directory Sum
      • Largest Subtree
      • Shortest Path DAG Source to Sink
      • HTML Parser
      • Infix to Postfix Expression Evaluater
      • Longest Path in Undirected Acyclic Graph
      • Decompress String
      • Pythagoras Tree
      • Kings
      • All Paths
      • Leaf Nodes
      • Proper Locking
      • Number of Cities at each Distance
      • Root Path as DLL
      • Binary Replacement
      • All Root to Leaf Paths
    • Recursion and Dynamic Programming
      • Recursive to_string
      • N Loop
      • Divisible by Set
      • Brute Force Seam Carving
      • Perimeter Island
      • Knight on a Phone
      • Coin Change Problem
      • Maximum Product in Matrix
      • Largest Sum of a Path in a Triangle
      • Linked List Tree
    • Sorting and Searching
      • Three Highest Numbers
      • Common Elements in Sorted Arrays
      • Inverse Spiral Matrix
      • Number Negatives in Sorted Matrix
      • Number of Bombs in Minesweeper
      • Two Sum Less Than
      • Frequency Compression
      • N Closest Points
      • Find Sum Pairs
      • Max with no Comparitor
      • Largest Subarray
      • Single Missing Number
      • Ternary Search
      • Fastest Frog Jump
    • Design
      • Random Hash DS
      • Road Trip
      • Load Balancer
      • Haircut Appointment Scheduler
      • Conway's Game of Life
      • Design Twitter
      • LogParser
      • Permission Management for a General Tree
      • Max Stack
      • Parking Lot
    • Probability
      • Simplified Blackjack
      • Rand7
      • Shuffle
    • Combinatorics
      • Binary Permutation
      • N Queens
      • Prefix Permutation
    • Mathematics
      • Angle Between Time
      • Line Segment Intersection
      • Maximum Points View Angle
      • Collatz Conjecture
      • Convex Hull
      • Swap In Place
      • Powers of 2
      • Monte Carlo Approximation of PI
      • Perfect Power
      • Derivative of a Polynomial
    • Bit Manipulation
      • Reverse Binary
    • Cryptography
      • Message Encyption and Decryption
      • Encryption
    • Other
      • Maximum Time Combination
      • Polish Notation String Calculator
  • Competition
    • CodeDavis
  • Project Eular
    • 1 Multiples of 3 and 5
    • 2 Even Fibonacci numbers
    • 3 Largest Prime Factor
    • 4 Largest Palindrome Product
    • 5 Smallest Multiple
    • 6 Sum Square Difference
    • 7 10001st Prime
    • 8 Largest Product in a Series
    • 9 Special Pythagorean Triplet
    • 10 Summation of Primes
    • 11 Largest Product in a Grid
    • 12 Highly Divisible Triangular Number
    • 13 Large Sum
    • 14 Longest Collatz Sequence
    • 15 Lattice Paths
    • 16 Power Digit Sum
    • 17 Number Letter Counts
    • 18 Maximum path sum I
    • 19 Counting Sundays
Powered by GitBook
On this page

Was this helpful?

  1. LeetCode

40 Combination Sum II

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

Each number inCmay only be usedoncein 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 target8, A solution set is:

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
  • These I thought this was a really great problem, I wrote about the details of my implementation in my other book Algorithms and Data Structures B.

struct Key
{
    Key() {};
    Key(const int val, const int iter, const int sum) :
        val(val), iter(iter), sum(sum) {}

    int val, iter, sum;

    bool operator==(const Key &other) const
    {
        return (val == other.val
            && iter == other.iter
            && sum == other.sum);
    }
};

namespace std {
    template <>
    struct hash<Key>
    {
        std::size_t operator()(const Key& k) const
        {
            return ((hash<int>()(k.val)
                ^ (hash<int>()(k.iter) << 1)) >> 1)
                ^ (hash<int>()(k.sum) << 1);
        }
    };

}

struct TreeNode2 {

    TreeNode2(Key key) : 
        key(key) {}
    TreeNode2() {};

    Key key;
    vector<TreeNode2 *> children;
};

class CombinationTree {

public:

    explicit CombinationTree(vector<int> nums, int target) :
        target(target) {

        root = new TreeNode2();
        sort(nums.begin(), nums.end());
        elms = nums;

        for (int i = 0; i < nums.size() && nums.at(i) <= target; i++) {
            Key key = Key(nums.at(i), i, nums.at(i));
            TreeNode2 *base_node = new TreeNode2(key);


            // identifing another subpath within a prebuilt path
            // but the idea is that if we put this path from the root
            // the it will become part of the valid set when
            // seaching all the root to leaf paths
            if (dp_hash_map.find(key) != dp_hash_map.end()) {
                root->children.push_back(dp_hash_map[key]);
                continue; // subtree exist
            }
            dp_hash_map.insert(make_pair(key, base_node));
            root->children.push_back(base_node);
            base_node->children = build_combination_tree(base_node);
        }
    }

    vector<vector<int>> root_leaf_paths(TreeNode2 *root, int target) {
        // good idea to use static parameters here (single reference)
        // just need to make sure to reset on deconstruction
        vector<vector<int>> main;
        vector<int> temp;
        unordered_set<string> unique_paths;
        string temp_str = "";

        // ignore the root
        for (TreeNode2 *n : root->children)
            root_leaf_paths_rec(n, temp, main, target, unique_paths, temp_str);

        return main;
    }

    static void print_level_order(TreeNode2 *root)
    {
        if (!root) return;
        cout << "Value:Iterator:Accumulative Sum:Number Children" << endl << endl;
        queue<TreeNode2*> q;
        q.push(root);
        q.push(nullptr);

        while (!q.empty()) {
            TreeNode2 *temp = q.front();
            if (temp)
                cout << temp->key.val << ":" << 
                temp->key.iter << ":" << temp->key.sum << ":" 
                << temp->children.size() << "  ";
            q.pop();

            if (temp) {
                for (TreeNode2 *t : temp->children) 
                    if (t) q.push(t);
            }
            else {
                if (!q.empty() && q.front()) {
                    q.push(nullptr);
                    cout << endl;
                }
            }
        }
    }

    TreeNode2 *root;

private:

    vector<int> elms;
    unordered_map<Key, TreeNode2*> dp_hash_map;
    int target;

    vector<TreeNode2*> build_combination_tree(TreeNode2* cur_node)
    {
        // current node attributes
        int cur_iter = cur_node->key.iter;
        int cur_sum = cur_node->key.sum;
        int cur_val = cur_node->key.val;

        vector<TreeNode2*> next_children;

        for (int i = cur_iter + 1; i < elms.size() && cur_sum < target; i++) {

            // if the sub tree exists, then do not bother creating
            // the same subtree for it
            Key key = Key(elms.at(i), i, cur_sum + elms.at(i));
            if (dp_hash_map.find(key) != dp_hash_map.end()) {
                // point to the already developed subtree, and continue.
                next_children.push_back(dp_hash_map[key]);
            }
            else {
                TreeNode2* next_node = new TreeNode2(key);
                dp_hash_map.insert(make_pair(key, next_node));
                next_children.push_back(next_node);
                next_node->children = build_combination_tree(next_node);
            }
        }

        return next_children;
    }


    /*
     * Performs traversal of combination tree
     * to collect valid summations
     */
    void root_leaf_paths_rec(TreeNode2 *root, 
        vector<int> &temp, 
        vector<vector<int>> &main, const int target, 
        unordered_set<string> &unique_paths,
        string &temp_str) {

        if (root) {
            temp_str += to_string(root->key.val) + " ";
            temp.push_back(root->key.val);
            if (root->children.empty() && root->key.sum == target
                && unique_paths.find(temp_str) == unique_paths.end()) {

                main.push_back(temp);
                unique_paths.insert(temp_str);

                temp.pop_back();
                pop_back_last_num(temp_str);
                return;
            }
            for (TreeNode2 *t : root->children) {
                if (t) root_leaf_paths_rec(t, temp, main, target, unique_paths, temp_str);
            }
        }
        temp.pop_back();
        pop_back_last_num(temp_str);
    }

    void pop_back_last_num(string &complete_str)
    {
        int iter = complete_str.length() - 2; // ignore first space
        while (iter >= 0 && complete_str.at(iter) != ' ') 
            iter--;

        complete_str = complete_str.substr(0, max(0,iter + 1));
    }
};

Some Testing:

vector<vector<int>> combinationSum2(vector<int>& candidates, int target)
{
    CombinationTree t = CombinationTree(candidates, target);
    //t.print_level_order(t.root);
    return t.root_leaf_paths(t.root, target);
}

int main(int argc, char **argv)
{
    vector<int> test1 = { 10, 1, 2, 7, 6, 1, 5 };
    print2d(combinationSum2(test1, 8));

    vector<int> test2 = { 1,1,2 };
    print2d(combinationSum2(test2, 3));

    vector<int> test3 = { 1,-2,3,4,-5,6,7,-8,90,-23,45,67,89 };
    print2d(combinationSum2(test3, 6));
}
Previous38 Count and SayNext41 First Missing Positive

Last updated 5 years ago

Was this helpful?