cpp/recursion/all_letter

Viewing cpp/recursion/all_letter_combos by redekopp@usc.edu. You have unsaved changes. Log in above to create, edit, preview and publish Websheets.

Property Value

Description
html markup
shown to student

<div>
Given a set of characters, <tt>letters</tt> in a vector and an integer length <tt>n</tt>, print out all the n-length combinations of letters

For example, if n=2 and letters contains:
<pre>
U S C
</pre>

Print the output:

<pre>
UU
US
UC
SU
SS
SC
CU
CS
CC
</pre>

Use recursion to solve the problem. Write the function:

<pre>
void allCombos(const vector<char>& letters, int n);
</pre>

You will likely need a helper function (looking at the function signature of <tt>allCombos</tt> you should see it lacks a needed parameter to build up the combination).

Recall the general recipe for generating all n-length combinations of a set, S, of options:

<ol>
<li>Base case: If the current combination is length, n
<li>Recursive case: If the current combination's length is less-than n, then iterate through the options in S:

<ol>
<li>Try adding the i-th option in S to the current combination</li>
<li>Recurse </li>
<li>Remove that option from the combination and repeat for the i+1-th option in S
</ol>
</ol>

Epilogue
html markup
shown when solved

remove
Public permissions remove
Remarks
Comments, history, license, etc.

Copied from problem cpp/recursion/prime_products_print (author: redekopp@usc.edu)
Copied from problem cpp/recursion/prime_products (author: redekopp@usc.edu)
Copied from problem cpp/recursion/zero_sum (author: daveagp@gmail.com)

remove
Engine
Choices
json list of string, bool pairs
e.g. [["good", true], ["bad", false]]

Correct answer
Template / Reference solution

Template / Reference solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

// add a helper function here if needed
\[
void allCombosHelper(const vector<char>& letters, int n, string curr)
{
if(n == curr.size()){
cout << curr << endl;
}
else {
for(unsigned int i=0; i < letters.size(); i++){
// The general pattern is:
// - try adding the i-th option (letter in this case)
// - recurse with the new 'curr' value
// - upon return, remove the i-th option and try the i+1-th
//
// Here we do that all in one line since 'curr' is passed by
// value we can make a temp string with the i-th letter
// and pass that copy leaving curr unchanged and ready for
// for the next iteration (i.e. for the i+1-th letter)
allCombosHelper(letters, n, curr+letters[i]);
}
}
}
]\

// Should generate all n-length combinations of letters
// in the given vector
void allCombos(const vector<char>& letters, int n)
{
\[
allCombosHelper(letters, n, "");
]\
}

int main(int argc, char* argv[]) {

int n;
char c;
vector<char> options;

// read the desired length
cin >> n;

// read the options
while(cin >> c) options.push_back(c);

allCombos(options, n);

return 0;
}

Java test suite
See manual

C++ test suite
json list of stdin/args tests
e.g. [{"stdin":"hi", "args":["4", "5"]}, {"stdin":"noargs"}]
to just run once with no input use [{}]

[
{"stdin":"2 USC"},
{"stdin":"4 AB"},
{"stdin":"5 *"}
]

C++ test suite
See manual

Forbidden substrings
json list of strings
e.g. ["for","while"]

remove
Solution visibility remove
Java imports
json list of importables
e.g. ["java.util.*"]

remove
Override Java classname
else defaults to
websheet name
remove
Dependent on other websheets?
json list of websheet names in this folder
e.g. ["DataStructure"]

remove
Is example?
i.e., just a demo
remove
Add compiler flag(s)
json list of flags
e.g. ["-Wno-unused-variable"]

remove
Remove default compiler flag(s)
json list of flags
see default_cppflags
e.g. ["-Wno-write-strings"]

remove

Property	Value
Description html markup shown to student	<div> Given a set of characters, <tt>letters</tt> in a vector and an integer length <tt>n</tt>, print out all the n-length combinations of letters <p> For example, if n=2 and letters contains: <pre> U S C </pre> Print the output: <pre> UU US UC SU SS SC CU CS CC </pre> Use recursion to solve the problem. Write the function: <pre> void allCombos(const vector<char>& letters, int n); </pre> You will likely need a helper function (looking at the function signature of <tt>allCombos</tt> you should see it lacks a needed parameter to build up the combination). <p> Recall the general recipe for generating all n-length combinations of a set, <em>S</em>, of options: <ol> <li><strong>Base case:</strong> If the current combination is length, n <li><strong>Recursive case:</strong> If the current combination's length is less-than n, then iterate through the options in <em>S</em>: <ol> <li>Try adding the i-th option in <em>S</em> to the current combination</li> <li>Recurse </li> <li>Remove that option from the combination and repeat for the i+1-th option in <em>S</em> </ol> </ol>
Epilogue html markup shown when solved	remove
Public permissions	remove
Remarks Comments, history, license, etc.	Copied from problem cpp/recursion/prime_products_print (author: redekopp@usc.edu) Copied from problem cpp/recursion/prime_products (author: redekopp@usc.edu) Copied from problem cpp/recursion/zero_sum (author: daveagp@gmail.com) remove
Engine
Choices json list of string, bool pairs e.g. `[["good", true], ["bad", false]]`
Correct answer
Template / Reference solution
Template / Reference solution	#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; // add a helper function here if needed \[ void allCombosHelper(const vector<char>& letters, int n, string curr) { if(n == curr.size()){ cout << curr << endl; } else { for(unsigned int i=0; i < letters.size(); i++){ // The general pattern is: // - try adding the i-th option (letter in this case) // - recurse with the new 'curr' value // - upon return, remove the i-th option and try the i+1-th // // Here we do that all in one line since 'curr' is passed by // value we can make a temp string with the i-th letter // and pass that copy leaving curr unchanged and ready for // for the next iteration (i.e. for the i+1-th letter) allCombosHelper(letters, n, curr+letters[i]); } } } ]\ // Should generate all n-length combinations of letters // in the given vector void allCombos(const vector<char>& letters, int n) { \[ allCombosHelper(letters, n, ""); ]\ } int main(int argc, char* argv[]) { int n; char c; vector<char> options; // read the desired length cin >> n; // read the options while(cin >> c) options.push_back(c); allCombos(options, n); return 0; }
Java test suite See manual
C++ test suite json list of stdin/args tests e.g. `[{"stdin":"hi", "args":["4", "5"]}, {"stdin":"noargs"}]` to just run once with no input use `[{}]`	[ {"stdin":"2 USC"}, {"stdin":"4 AB"}, {"stdin":"5 *"} ]
C++ test suite See manual
Forbidden substrings json list of strings e.g. `["for","while"]`	remove
Solution visibility	remove
Java imports json list of importables e.g. `["java.util.*"]`	remove
Override Java classname else defaults to websheet name	remove
Dependent on other websheets? json list of websheet names in this folder e.g. `["DataStructure"]`	remove
Is example? i.e., just a demo	remove
Add compiler flag(s) json list of flags e.g. `["-Wno-unused-variable"]`	remove
Remove default compiler flag(s) json list of flags see default_cppflags e.g. `["-Wno-write-strings"]`	remove

Optional properties:

Note: problems are open-source by default (see 'Public permissions'). Assumed license for open problems is Creative Commons 4.0 Attribution-ShareAlike unless specified in 'Remarks'.